《C语言求素数问题算法》由会员分享，可在线阅读，更多相关《C语言求素数问题算法（8页珍藏版）》请在金锄头文库上搜索。
1、如何求素数如何求素数1 自然数是 0，1，22 素数是 2，3，5（不包括 1 的只能背 1 和它本身整除的自然数）#include#include void main()int i ,j, flag=1;for(i=101; iNNN。而这是不可能的，所以，d1 和 d2 中必有一个小于或等于N。基于上述分析，设计算法如下：(1)用 2，3，5，7 逐个试除 N 的方法求出 100 以内的所有素数。(2)用 100 以内的所有素数逐个试除的方法求出 10000 以内的素数。首先，将 2，3，5，7 分别存放在 a1、a2、a3、a4中，以后每求出一个素数，只要不大于 100，就依次存放在A
2、数组中的一个单元 中。当我们求 10010000 之间的素数时，可依次用 a1a2的素数去试除 N，这个范围内的素数可以不保存，直接打印。【2】用筛法求素数。用筛法求素数。简单介绍一下厄拉多塞筛法。厄拉多塞是一位古希腊数学家，他在寻找素数时，采用了一种与众不同的方法：先将 2N的各数写在纸上：在 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，6N+1，6N+2，6N+3，6N
4、+4，6N+5 (N=0，1，2，)显然，当 N1 时，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 isPrime(int n)if(n sqrt(n)范围内的所有素数bool isPrime(int primes, int n)if(n = 67 时.因此 O(PI(sqrt(n)可以表示为 O(sqrt(x)/(ln(sqrt(x)-3/2),O(sqrt(x)/(ln(sqrt(x)-3/2)也是这个算法的空间复杂度.5. 构造素数序列 primesi: 2, 3, 5, 7, .由 4 的算法我们知道, 在
6、素数序列已经被构造的情况下, 判断 n 是否为素数效率很高;但是, 在构造素数序列本身的时候, 是否也可是达到最好的效率呢?事实上这是可以的! - 我们在构造的时候完全可以利用已经被构造的素数序列!假设我们已经我素数序列: p1, p2, . pn现在要判断 pn+1 是否是素数, 则需要(1, sqrt(pn+1)范围内的所有素数序列,而这个素数序列显然已经作为 p1, p2, . pn 的一个子集被包含了!代码:/ 构造素数序列 primesvoid makePrimes(int primes, int num)int i, j, temp;primes0 = 2;primes1 = 3;
7、for(i = 5, temp = 2; temp 232, (232 = 4294967296)在实际运算时 unsigned long x = 4295098369;将发生溢出, 为 131073.在程序中, 我是采用 double 类型计算得到的结果.分析到这里我们可以看到, 我们只需要缓冲 6543 个素数, 我们就可以采用 4 中的算法高效率地判断2, 232如此庞大范围内的素数!(原本的 232 大小的问题规模现在已经被减小到 6543 规模了!)虽然用现在的计算机处理2, 216范围内的 6542 个素数已经没有一点问题,虽然 makePrimes 只要被运行一次就可以, 但是我
8、们还是考虑一下是否被改进的可能?!我想学过 java 的人肯定想把 makePrimes 作为一个静态的初始化实现, 在 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
9、 函数呢?完全可以! 代码如下:/ 这段代码可以由程序直接生成const static int primes = 2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101,103,107,109,113,127,131,137,139,149,151,157,163,167,173,179,181,191,193,197,199,211,223,227,229,233,239,241,251,257,263,269,271,277,281,283,293,307,311,313,317,331,337,
10、347,349,353,359,367,373,379,383,389,397,401,409,419,421,431,433,439,443,449,457,461,463,467,479,487,491,499,503,509,521,523,541,547,557,563,569,571,577,587,593,599,601,607,613,617,619,631,641,643,647,653,659,661,673,677,683,691,701,709,719,727,733,739,743,751,757,761,769,773,787,797,809,811,821,823,
11、827,829,839,853,857,859,863,877,881,883,887,907,911,919,929,937,941,947,953,967,971,977,983,991,.65521, 65537;有点不可思议吧, 原本 makePrimes 需要花费的时间复杂度现在真的变成 O(1)了!(我觉得叫 O(0)可能更合适!)7. 二分法查找现在我们缓存了前大约 sqrt(232)/(ln(sqrt(232)-3/2)个素数列表, 在判断 232 级别的素数时最多也只需要PI(sqrt(232)次判断(准确值是 6543 次), 但是否还有其他的方式判断呢?当素数比较小的时候
12、(不大于 216), 是否可以直接从缓存的素数列表中直接查询得到呢?答案是肯定的! 由于 primes 是一个有序的数列, 因此我们当素数小于 216 时, 我们可以直接采用二分法从 primes 中查询得到(如果查询失败则不是素数).代码:/ 缺少的代码请参考前边#include static bool cmp(const int *p, const int *q)return (*p) - (*q);bool isPrime(int n)if(n = 67 / bsearch 的比较函数static int cmp(const void *p, const void *q)return (
13、*(int*)p) - (*(int*)q);/ 缓冲的素数个数int Prime_max()return NELEMS(primes);/ 返回第 i 个素数int Prime_get(int i)assert(i = 0 if(n = 67 是才满足素数定理if(n = 67) lo = (int)floor(n/(log(n)-1/2.0);else lo = 0; hi = 19; / 查找成功则为素数return NULL !=bsearch(else / 不在保存的素数序列范围之内的情况for(int i = 1; primesi*primesi = n; +i)if(n%prim
14、esi = 0) return false;return true;10. 回顾, 以及推广到这里, 关于素数的讨论基本告一段落. 回顾我们之前的求解过程, 我们会发现如果缺少数学的基本知识会很难设计好的算法; 但是如果一味地只考虑数学原理,而忽律了计算机的本质特征, 也会有同样的问题.一个很常见的例子就是求Fibonacci 数列. 当然方法很多, 但是在目前的计算机中都没有实现的必要!因为 Fibonacci 数列本身是指数增长的, 32 位的有符号整数所能表示的位置只有前 46 个:代码:static const int Fibonacci = 0,1,1,2,3,5,8,13,21,3
15、4,55,89,144,233,377,610,987,1597,2584,4181,6765,10946,17711,28657,46368,75025,121393,196418,317811,514229,832040,1346269,2178309,3524578,5702887,9227465,14930352,24157817,39088169,63245986,102334155,165580141,267914296,433494437,701408733,1134903170,1836311903,-1323752223;因此, 我只需要把前 46 个 Fibonacci 数保存到数组中就可以搞定了!比如: F(int i) = return Fibonaccii; 非常简单, 效率也非常好.
