首页 > 编程知识 正文

最小的素数是1还是2,素数个数计算公式

时间:2023-05-05 19:29:57 阅读:61946 作者:344

素数最简单的判断方法采用枚举,复杂度为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 )

版权声明:该文观点仅代表作者本人。处理文章:请发送邮件至 三1五14八八95#扣扣.com 举报,一经查实,本站将立刻删除。