草丁图书馆

  1. 首页 > 生活杂烩 >

如何判断一个数是不是质数，什么是质数?( 三 )

小知识


对179试除过程如下：
179÷2=59……2
179÷3=66……1
179÷5=35……4
179÷7=25……4
179÷11=16……3
179÷13=13……10
179÷17=10……9
当179÷17所得到的不完全商10比除数17小时 ， 就不需要继续再试除 ， 而断定179是质数 。 这是因为2、3、5、7、11、13、17都不是179的质因数 ， 因此 ， 179不会再有比17大的质因数 ， 或者说179不可能被小于10的数整除 ， 所以 ， 179必是质数无疑 。
综上所述 ， 用试除法判断一个自然数a是不是质数时 ， 只要用各个质数从小到大依次去除a ， 如果到某一个质数正好整除 ， 这个a就可以断定不是质数；如果不能整除 ， 当不完全商又小于这个质数时 ， 就不必再继续试除 ， 可以断定a必然是质数 。
怎样判断一个数字是不是质数 下面是我用JavaScript写的素数函数 ， 供参考 ， 大同小异
PrimeA=function(n,nth){/* 小于n的素数表
参数nth 指定返回第n个素数

*/
//var t0=Time.now5();
/*
方法1：利用isPrime 废弃！

var t=[];
for(var i=2;i<n+1;i++){
if(isPrime(i)){
t.push(i)
}
}
consolelog('方法1：耗时：'+(+Time.now5()-(+t0)));
return t
*/

//方法2：利用筛法
var p=[2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59];//自己往后补充 ， 越多越好 ， 可以加快检测小素数的效率
if(nth && n<=669){
return p[n-1]
}
if(!nth && n<2){
return []
}

if(n<=5000 && !nth){

for(var i=0;i<100;i++){
var j=p.indexOf(n-i);
if(j>-1){return p.slice(0,j+1)};
}
return p
}

var m=nth?Math.ceil(n*Math.log(n)+1000):n; //pn ～ nln(n)
// for(var i=5001;i<=m;i+=2){
var i=5001;
while(i){
var t=Math.floor(Math.sqrt(i)), pl=p.length;
for(var j=0;j<pl;j++){//p.length
if(i%p[j] == 0){
break
}else if(p[j+1]>t){
p.push(i);
if(nth && pl==n-1){
return i
}
break;
}
}
if(!nth && i>=n-1){
return p
}
i+=2;
}
return p


//方法3：Wilson测试


}
c语言中如何判断一个数是否是质数？ n 为要验证的数
For i = 2 To Int(Sqr(n))
'从2开始 ， 到根号n（取整数）循环
I f n Mod i = 0 Then Exit For
’如果i除n的余数为0 ， 则退出循环
Next i
If i > Int(Sqr(n)) Then
'如果i>根号n（取整数）,说明没有提前退出循环
Print n & 不是素数;
'打印：
End If
如何用C++判断一个数是不是质数（素数） 1、查表法：
主要是指查“质数表” 。 编制质数表的过程是：按照自然数列 ， 第一个数1不是质数 ， 因此要除外 ， 然后按顺序写出2至100的所有自然数 ， 这些数中2是质数 ， 把它留下 ， 把2后面所有2的倍数划去 ， 2后面的3是质数 ， 接着再把3后面所有3的倍数划去 ， 如此继续下去 ， 剩下的便是100以内的全部质数 。
2、试除法：
在手头上没有质数表的情况下 ， 可以用试除法来判断一个自然数是不是质数 。 例如判断143、179是不是质数 ， 就可以按从小到大的顺序用2、3、5、7、11……等质数去试除 。 一般情况下用20以内的2、3、5、7、11、13、17、19这8个质数去除就可以了 。
如143 ， 这个数的个位是3 ， 排除了被2、5整除的可能性 ， 它各位数字的和是1+4+3=8 ， 也不可能被3整除 ， 通过口算也证明不能被7整除 ， 当试除到11时 ， 商正好是13 ， 到此就可以断定143不是质数 。
扩展资料：
一、质数的相关性质

1、质数p的约数只有两个：1和p 。

推荐阅读


上一篇：【花卉大全】枝干的根部和稍部粗细相同

下一篇：【花卉大全】轻轻一挠即可