BYR Achieve · 镜像论坛

今天仔细研究了一下素数的问题，得到一些心得写下来： 1.暴力枚举思路：一个一个去测试到n ,能整除就不是，最后都不能整除的就是素数； 2.暴力枚举思路：一个一个去测试到sqrt(n) ,能整除就不是，最后都不能整除的就是素数；总结：稍微有点改进，但是复杂度依然很高 3.算术基本定理详见：http://baike.baidu.com/link?url=sJLGSh3YXpsTO40Pw8F9ZBQVe- KjFgY4kaXgO65_vjyNvtFemEYVw0okmK0O0bmZwhcWiCcXgZgXivlMlg9wia 思路：一个合数能唯一表示成素因子之积的形式，所以开个数组存下小于n的素数，然后测试，能整除就不是，最后都不能整除的就是素数；代码如下： #include <stdio.h> #define N 1000005 int p[N]; int main() { int n=1000000; int i,j,k; int num=0; p[num++]=2; for(i=3;i<=n;i++) { for(j=0;j<num;j++) { if(!(i%2)) break; if(i%p[j]==0) break; } if(j==num) p[num++]=i; } /*for(k=0;k<num;k++) { if(p[k]>n) break; printf("%d\n",p[k]); }*/ printf("素数个数为：%d\n",num); return 0; } 总结：每次取余的时候如果遇到后边素数的倍数就要查询好久，在n=100万时已经运行了13s 改进：如果能找到一个直接它的素因子就很好了，这就要用到筛法了 4.筛法详见：http://baike.baidu.com/view/82625.htm 思路：筛去2,3，。。。，sqrt（n）的倍数，剩下的就是素数代码： #include <stdio.h> #include <math.h> #define N 100000000 int r[N]; int main() { int n=10000000; int i,j; int num; int count=0; num=sqrt(n); for(i=2;i<=num;i++) { if(r[i]) continue; for(j=2;i*j<=n;j++) { if(r[i*j]) continue; r[i*j]=1; } } for(i=2;i<=n;i++) { if(!r[i]) { /*printf("%d\n",i);*/ count++; } } printf("1-%d的素数个数为：%d\n",n,count); return 0; } 总结：n=1000万只有0.374s，已经非常快了改进：筛的时候会重复筛选后边的倍数，比如2和3的公倍数6就筛了两遍 5.线性筛思路：结合筛法和算术基本定理合数=第一个素因子*合数/合数=素数*素数保证每个元素只访问一次更多信息可见：http://blog.csdn.net/nuanxin_520/article/details/41207145 代码： #include <stdio.h> #define N 10000000 int p[N]; int is[N]; int main() { int n=10000000; int i,j; int num=0; is[0]=is[1]=1; for(i=2;i<=n;i++) { if(!is[i]) p[num++]=i; for(j=0;j<num&&i*p[j]<=n;j++) { is[i*p[j]]=1; if(!(i%p[j])) break; } } printf("1-%d的素数个数为:%d\n",n,num); return 0; } 比较：n=1亿时筛法用时2.664s，线性筛用时1.326s，不同编译器或者电脑配置可能稍有不同，但是已经能体现优越性了，数据更大的话应该更明显，大于一亿的数组开不了了，未能验证，不过结果应该正确。注意：数据量小的时候可能筛法更快，应该是因为筛法只能到了加法和乘法，而线性筛还用了取余操作会比较费时还有更多更好的办法有待学习，不过平时使用已经满足需求了记：所有程序均在win7，codeblocks上运行

统计小于等于n的素数个数问题