| 素数个数统计的三种方法 | 您所在的位置：网站首页 › 求1-300中所有素数的平均值 › 素数个数统计的三种方法 |
素数个数统计的三种方法
|
目录
引言问题引入算法1.暴力算法2.埃氏筛选3.欧氏筛选输出结果
后记
引言
最近在学习数据结构与算法，偶然看到素数筛选的题目，在阅读了多位大佬的博文后总结了素数筛选的三种算法。其中有一些个人的理解，如有错误，还请大家不吝赐教。 问题引入统计n以内的素数个数，0、1除外 例：输入：100 输出：25 算法 1.暴力算法暴力算法即遍历寻找素数的个数。在判断某一个数是否为素数时，只需要从2开始，遍历到 n \sqrt{n} n 。举个例子，合数8，可以是2*4，也可以是4*2,当判断了2为该数的一个质因子后，该数就已经被认为不是素数了，后面的4也就没有必要判断了，而这个判断的分界点恰好就是 n \sqrt{n} n 。而在C语言中j flag = 1;//先假定该数为素数 for (j = 2; j * j flag = 0;//flag==0说明这个数是合数 break; } } if (flag) count++; } printf("暴力算法 %d以内有%d个素数\n", n, count); } 可以注意到，素数除了2以外都是奇数，因此，我们可以对暴力算法优化一下 void brute_force(int n)//暴力算法(优化后) { int count = 0; int i,j; int flag = 1; if (n >=2) count++; for (i = 3; i if (i % j == 0) { flag = 0; break; } } if (flag) count++; } printf("暴力算法 %d以内有%d个素数\n", n, count); } 2.埃氏筛选埃氏筛选的主要思想是先把n以内的合数全部找出来，合数排除以后，其余的就全部是素数了，运用的方法是以空间换时间。 实现方式：首先建立一个数组用以储存n以内的数的状态，如果是合数，则该以该数为下标的数值为1。如果不是合数，则为素数，值为0。通过这个素数i，去筛选出n以内以i为质因子的合数（2*i,3*i,……） 在埃氏筛选中，若内层循环的j是从2*i开始，则时间复杂度为O(n log n \log{n} logn); 若内层循环j是从i*i开始，则时间复杂度为O(n l o g l o g n log{log{n}} loglogn) void eratosthenes(int n)//埃氏筛选 { int no_prime[10000] = {0};//先假定全部为素数。找到一个数不是素数，就把这个值变为1 int i, j; int count = 0; for (i = 2; i count++; for (j = i * i; j 0};//标记数，开始假定全部为素数 int count = 0; int i, j; for (i = 2; i no_prime[i * is_prime[j]] = 1; if (i % is_prime[j] == 0)//关键，保证每一个数只被它的最小质因子筛出 break; } } printf("\n欧氏筛选 %d以内有%d个素数", n, count); } 输出结果
暴力算法容易理解，但效率最低；埃氏筛选虽提高了效率，但在内层循环j=i*i中,若筛选大数时，则会出现数据溢出的情况；欧氏筛选即为线性筛选，时间复杂度是三种算法中最低的，但需要好好理解if语句的功能。 筛选素数的方法除了以上三种以外还有很多，本文未提及的还有寻找区间内素数个数的筛选算法。 第一次写文章，在加深理解的同时，希望对读者有所帮助。 参考： Eratosthenes筛法(埃式筛法)时间复杂度分析 |
【本文地址】