c语言求素数问题算法

如何求素数 1 自然数是 0，1，2 2 素数是 2，3，5 （不包括 1 的只能背 1 和它本身整除的自然数） #include #include void main() int i ,j, flag=1; for(i=101; iNN N 。 而这是不可能的，所以，d1 和 d2 中必有一个小于或等于N 。 基于上述分析，设计算法如下： (1)用 2，3，5，7 逐个试除 N 的方法求出 100 以内的所有素数。 (2)用 100 以内的所有素数逐个试除的方法求出 10000 以内的素数。 首先，将 2，3，5，7 分别存放在 a1、a2 、a3、a4中，以后每求出一个素数，只要不大于 100，就依次存放在 A 数组中的一个单元 中。当我们求 10010000 之间的素数时，可依次用 a1a2的素数去试除 N，这个范围内的 素数可以不保存，直接打印。 【2】用筛法求素数。 简单介绍一下厄拉多塞筛法。厄拉多塞是一位古希腊数学家，他在寻找素数时，采用了一种与众不同的方法：先将 2N 的各数写在纸上： 在 2 的上面画一个圆圈，然后划去 2 的其他倍数；第一个既未画圈又没有被划去的数是 3，将它画圈，再划去 3 的其他倍 数；现在既未画圈又没有被划去的第一个数 是 5，将它画圈，并划去 5 的其他倍数 依次类推，一直到所有小于或等于 N 的各数都画了圈或划去为止。这时，表中画了圈的以及未划去的那些数正好就是小于 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 ，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 的自然数。 浅析求素数算法 注意: 如果没有特殊说明, 以下讨论的都是针对 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 的算法我们知道, 在素数序列已经被构造的情况下, 判断 n 是否为素数效率很高; 但是, 在构造素数序列本身的时候, 是否也可是达到最好的效率呢? 事实上这是可以的! - 我们在构造的时候完全可以利用已经被构造的素数序列! 假设我们已经我素数序列: p1, p2, pn 现在要判断 pn+1 是否是素数, 则需要(1, sqrt(pn+1)范围内的所有素数序列, 而这个素数序列显然已经作为 p1, p2, pn 的一个子集被包含了! 代码: / 构造素数序列 primes void makePrimes(int primes, int num) int i, j, temp; primes0 = 2; primes1 = 3; 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 只要被运行一次就可以, 但是我们还是考虑一下是否被改进的可能?! 我想学过 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 函数呢? 完全可以! 代码如下: / 这段代码可以由程序直接生成 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,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,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 次), 但是否还有其他的方式判断呢?当素数比较小的时候(不大于 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 (*(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%primesi = 0) return false; return true; 10. 回顾, 以及推广 到这里, 关于素数的讨论基本告一段落. 回顾我们之前的求解过程, 我们会发现如果缺少数学的基本知识会很难设计好的 算法; 但是如果一味地只考虑数学原理,而忽律了计算机的本质特征 , 也会有同样的问题.一个很常见的例子就是求 Fibonacci 数列. 当然方法很多, 但是在目前的计算机中都没有实现的必要! 因为 Fibonacci 数列本身是指数增长的, 32 位的有符号整数所能表示的位置只有前 46 个: 代码: static const int Fibonacci = 0,1,1,2,3,5,8,13,21,34,55,89,144,233,377,610,987,1597, 2584,4181,6765,10946,17711,28657,46368,75025,121393,196418, 317811,514229,832040,1346269,2178309,352