素数筛法详解

素数筛法详解

我们直接抓住素筛的核心：

定理: 如果n不是素数, 则n有满足1算法终止. I3. 令n=d, 并转到步骤I1. 由于不可能无限分解n的因子, 因此上述证明的算法最终会停止. 代码:

// primes[i]是递增的素数序列: 2, 3, 5, 7, ...// 更准确地说primes[i]序列包含1->sqrt(n)范围内的所有素数// 如何高效构造primes[]？需要多少个素数才能判断2^31-1内的所有素数？一会会有说明int isPrime(int primes[], int n){ if(n < 2) return 0; for(int i = 0; primes[i]*primes[i] <= n; ++i) if(n % primes[i] == 0) return 0;//对应上述“n有素因子，n是合数” return 1;}

构造素数序列primes[i]: 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, cnt; primes[0] = 2; primes[1] = 3; for(i = 5, cnt = 2; cnt < num; i += 2)//cnt为primes下标，i+=2筛去了偶数 { int flag = 1; for(j = 0; primes[j]*primes[j] <= i; ++j) { if(i%primes[j] == 0) { flag = 0; break; } } if(flag) primes[cnt++] = i; }}

当前的主流PC中, 一个整数的大小为2^32. 如果需要判断2^32大小的数是否为素数,

则可能需要测试[2, 2^16]范围内的所有素数(2^16 == sqrt(2^32)).

在对[2, 2^16]范围内的素数进行统计, 发现只有6542个素数:

p_6542: 65521, 65521^2 = 4293001441 < 2^32, (2^32 = 4294967296)

p_6543: 65537, 65537^2 = 4295098369 > 2^32, (2^32 = 4294967296)（在实际运算时unsigned long x = 4295098369;将发生溢出, 为131073）

分析到这里我们可以看到, 我们只需要缓冲6543个素数, 我们就可以采用上述算法高效率地判断[2, 2^32]如此庞大范围内的素数!

(原本的2^32大小的问题规模现在已经被减小到6543规模了!)

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。