《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