《C语言求素数问题算法》由会员分享，可在线阅读，更多相关《C语言求素数问题算法（9页珍藏版）》请在金锄头文库上搜索。
1、如何求素数1. 自然数是0, 1, 22. 素数是2, 3, 5(不包括1的只能背1和它本身整除的自然数)# include# include void main()int i ,j, flag = 1;for (i = 101; i200; i +)flag = 1;for (j = 2; jVNxVN = N。而这是不可能的，所以，d1和d2中必有一个小于或等于VN。 基于上述分析，设计算法如下：(1) 用2, 3, 5, 7逐个试除N的方法求出100以内的所有素数。(2) 用100以内的所有素数逐个试除的方法求出10000以内的素数。首先，将2, 3, 5, 7分别存放在a1、a2、a3
2、、a4中，以后每求出一个素数，只要不大于100,就依次存放在A 数组中的一个单元中。当我们求10010000之间的素数时，可依次用a1-a2的素数去试除N,这个范围内的素数 可以不保存，直接打印。【 2】用筛法求素数。简单介绍一下厄拉多塞筛法。厄拉多塞是一位古希腊数学家，他在寻找素数时，采用了一种与众不同的方法：先将2 N的各数写在纸上：在 2 的上面画一个圆圈，然后划去 2 的其他倍数；第一个既未画圈又没有被划去的数是 3 ，将它画圈，再划去 3 的其他倍 数；现在既未画圈又没有被划去的第一个数是5,将它画圈，并划去5的其他倍数依次类推，一直到所有小于或等于N 的各数都画了圈或划去为止。这时
3、，表中画了圈的以及未划去的那些数正好就是小于 N 的素数。这很像一面筛子，把满足条件的数留下来，把不满足条件的数筛掉。由于这种方法是厄拉多塞首先发明的，所以，后人就把 这种方法称作厄拉多塞筛法。在计算机中，筛法可以用给数组单元置零的方法来实现。具体来说就是：首先开一个数组：ai，i = 1, 2, 3,，同时， 令所有的数组元素都等于下标值，即ai = i,当i不是素数时，令ai=0。当输出结果时，只要判断ai是否等于零即 可，如果ai=0,则令i = i+1,检查下一个ai。筛法是计算机程序设计中常用的算法之一。【3】用6N1法求素数。任何一个自然数，总可以表示成为如下的形式之一：6N， 6
4、N+1， 6N+2， 6N+3， 6N+4， 6N+5 (N=0， 1， 2， )显然，当NA1时，6N, 6N+2, 6N + 3, 6N+4都不是素数，只有形如6N + 1和6N + 5的自然数有可能是素数。所以， 除了 2和3之外，所有的素数都可以表示成6N1的形式(N为自然数)。根据上述分析，我们可以构造另一面筛子，只对形如6 N1的自然数进行筛选，这样就可以大大减少筛选的次数，从而进 一步提高程序的运行效率和速度。在程序上，我们可以用一个二重循环实现这一点，外循环i按3的倍数递增，内循环j为01的循环，则2(i+j)-1恰好 就是形如6N1的自然数。浅析求素数算法注意:如果没有特殊说
5、明，以下讨论的都是针对n为素数时的时间复杂度1. 根据概念判断：如果一个正整数只有两个因子，1和p,则称p为素数.代码：时间复杂度O(n).bool isP rime(int n)if(n 2) retu rn false;for (int i = 2; i n; +i)if(n%i = 0) retu rn false;retu rn tr ue;2. 改进，去掉偶数的判断代码：时间复杂度O(n/2),速度提高一倍.bool isP rime(int n) if(n 2) ret urn false;if(n = 2) return true;fo r(int i = 3; i n; i +
6、= 2)if(n%i = 0) retu rn false;retu rn tr ue;3. 进一步减少判断的范围定理：如果n不是素数，则n有满足1d=sqrt(n)的一个因子d.证明：如果n不是素数，则由定义n有一个因子d满足1dn.如果d大于sqrt(n),则n/d是满足1n/d=sqrt(n)的一个因子.代码：时间复杂度O(sqrt(n)/2),速度提高O(n-sqrt(n)/2)bool isP rime(int n)if(n 2) retu rn false;if(n = 2) retu rn tr ue;for(int i = 3; i*i = n; i += 2)/使用 ivsq
7、rt(n)if(n%i = 0) retu rn false;retu rn tr ue;4. 剔除因子中的重复判断? 例如： 11%3 != 0 可以确定 11%(3*i) != 0.定理：如果n不是素数，则n有满足1d=sqrt(n)的一个素数因子d.证明：11. 如果n不是素数，则n有满足1sqrt(n)范围内的所有素数bool isP rime(int pr imes, int n)if(n 2) retu rn false;for (int i = 0; pr imesi*p rimesi = n; +i)if(n%p rimesi = 0) return false;retu rn
8、 tr ue;假设n范围内的素数个数为PI(n),则时间复杂度O(PI(sqrt(n).函数 PI(x)满足素数定理:ln(x)-3/2 x/PI(x) = 67 时.因此 O(PI(sqrt(n)可以表示为 O(sqrt(x)/(ln(sqrt(x)-3/2),O(s qr t(x)/(ln(s qr t(x)-3/2)也是这个算法的空间复杂度.5. 构造素数序列 primesi： 2, 3, 5, 7, .由4的算法我们知道，在素数序列已经被构造的情况下，判断n是否为素数效率很高； 但是, 在构造素数序列本身的时候, 是否也可是达到最好的效率呢?事实上这是可以的! - 我们在构造的时候完全
9、可以利用已经被构造的素数序列! 假设我们已经我素数序列： p1, p2, . pn现在要判断pn + 1是否是素数，则需要(1, sqrt(pn + 1)范围内的所有素数序列，而这个素数序列显然已经作为p1, p2, . pn的一个子集被包含了！ 代码：/构造素数序列primesvoid makeP rimes(int pr imes, int num)int i, j, temp;pr imes0 = 2;pr imes1 = 3;在一定的应用范围内, 我们可以把近似认为 makePrimes 需要常数时间.在后面的讨论中, 我们将探讨一种对计算机而言更好的 makePrimes 方法.6.
10、 更好地利用计算机资源.当前的主流PC中，一个整数的大小为2人32.如果需要判断2人32大小的数是否为素数，则可能需要测试2, 2人16范围 内的所有素数(2人16 = sqrt(2人32).由4中提到的素数定理我们可以大概确定2, 2人16范围内的素数个数.由于 2人16/(ln(2人16)-1/2) = 6138, 2人16/(ln(2人16)-3/2) = 6834,我们可以大概估计出2, 2人16范围内的素数个数6138 PI(2人16) 6834.在对2, 2人16范围内的素数进行统计，发现只有6542个素数：p_6542: 65521, 65521人2 = 4293001441 2
11、人32,(2人32 = 4294967296)在实际运算时unsigned long x = 4295098369;将发生溢出，为131073.在程序中，我是采用double类型计算得到的结果.分析到这里我们可以看到, 我们只需要缓冲6543个素数, 我们就可以采用4中的算法高效率地判断2, 2人32如此庞大范围内的素数！(原本的2人32大小的问题规模现在已经被减小到6543规模了!)虽然用现在的计算机处理2, 2人16范围内的6542个素数已经没有一点问题，虽然makePrimes只要被运行一次就可以，但是我们还是考虑一下是否被改进的可能？！我想学过java的人肯定想把makePrimes作
12、为一个静态的初始化实现，在C+ +中也可以模拟java中静态的初始化的类似实现：#define NELEMS(x) (sizeof(x) / (sizeof(x)0)static int primes6542+1;static struct _Init _Init()makePrimes(primes, NELEMS(primes); _init;如此，就可以在程序启动的时候自动掉用makePrimes初始化素数序列.但，我现在的想法是：为什么我们不能在编译的时候调用makePrimes函数呢？完全可以!！代码如下：/这段代码可以由程序直接生成const static int pr imes=2,3,5,7,11,13,17,19,23,29,31,37
