素数最简单的判断方法采用枚举,复杂度为o(n )。 (这里不说明)
在此,对以下几点进行说明。
1 )素数判断,复杂度为o(n )的原理和代码。
2 )质数表的获取。
3 )用于更有效判断素数的“筛选法”。
(一)素数判断
这里介绍复杂度为o(n )的原理。
例:设在2~n-1中存在n的约数为k,即n%k==0,则从k*(n/k )=0开始,n/k也是n的约数,因此在k和n/k中,(一个数)小于n,一个数
在这里稍微说明一下。 对于n*n=n,k*n/k=n,所以一个约数小于n,一个约数大于n。
提示:只需判断n是否能被2,3 .|_n_|中的任意一个整除即可(其中|_n_|意味着向下四舍五入)。
在此为sqrt ) )请注意函数的使用方法。
1 )传递的参数必须是浮点型。
2 )返回类型也是浮点类型。
因此,请严格按照标准编写代码。
boolisprime(intn ) if ) n=1)返回假; intsqr=(int ) sqrt ) 1.0*n; for(intI=2; i=sqr; I ) if(n%I==0)返回假; }返回真; }也许还有其他更简单的写法。
boolisprime(intn ) if ) n=1)返回假; for(intI=2; i*i=n; I ) if(n%I==0)返回假; }返回真; )初学者建议不要用这个简单的写法。 原因是,当n接近int类型范围的边界时,i*i很可能发生越境溢出。 (当然n在10^9以内是绝对安全的)
但是,这也有解决办法。 把I定义为long long类型就可以了。
(二)获取表
方法:列举1~n,判断每个数是否为素数。
时间复杂度:由于是一部分o(n )和另一部分o(n ) n ) ),所以取得表的复杂度为o(n ) n ) )。
求# include stdio.h # include math.h//100以内素数表的boolisprime(int ); int prime[101],Num=0; void Find_Prime () {for ) intI=1; i101; I ) if(isprime(I )==true ) {prime[Num ]=i; }//n为素数boolisprime(intn ) ) if ) n=1) return false; intsqr=(int ) sqrt ) 1.0*n; for(intI=2; i=sqr; I ) if(n%I==0)返回假; }返回真; (}int main ) ) {Find_Prime ); for(intI=0; iNum; I ) (printf )、prime[i]; }返回0; }
(三)筛选法求素数
原理:列出从2到n的所有数量。 然后,从2开始。 首先,消除n中所有2的倍数。 然后,每次从下一个剩下的数(必然是素数)中消除该n内的所有倍数。 最后一个数都是素数。
具体流程:自己百度。
int prime[101],Num=0; bool p[101]={0}; //如何变成素数是指false void Find_Prime () for ) intI=2; i101; I () if ) p[I]==false ) ) {prime[Num ]=i; for(intj=II; j101; j=j i () {p[j]=true; } }时间的复杂度为o(nloglogn )