Joh*_*ith 38 algorithm primes sieve-of-eratosthenes prime-factoring factors
制作一个简单的筛子很容易:
for (int i=2; i<=N; i++){
if (sieve[i]==0){
cout << i << " is prime" << endl;
for (int j = i; j<=N; j+=i){
sieve[j]=1;
}
}
cout << i << " has " << sieve[i] << " distinct prime factors\n";
}
但是当N非常大并且我无法在内存中保存那种数组时呢？我已经查找了分段筛选方法,它们似乎涉及到找到素数直到sqrt(N),但我不明白它是如何工作的.如果N非常大(例如10 ^ 18)怎么办？
use*_*810 51
分段筛的基本思想是选择小于n的平方根的筛分质数,选择一个相当大的段大小但仍然适合记忆,然后依次筛选每个段,从最小的开始.在第一段,计算在该段内的每个筛分素数的最小倍数,然后以正常方式将筛分素数的倍数标记为复合物; 当所有筛选质数都被使用时,该段中剩余的未标记数字是素数.然后,对于下一个段,对于每个筛分素数,您已经知道当前片段中的第一个倍数(它是结束在前一个片段中筛选的素数的倍数),因此您筛选每个筛选素数,依此类推直到你完成.
n的大小无关紧要,除了较大的n比较小的n需要更长的筛子时间; 重要的大小是段的大小,它应该是方便的(例如,机器上的主存储器高速缓存的大小).
您可以在此处看到分段筛的简单实现.请注意,分段筛网将比另一个答案中提到的O'Neill优先排队筛网快得多; 如果你有兴趣,有一个执行在这里.
编辑:我写这个用于不同的目的,但我会在这里显示它,因为它可能是有用的:
尽管Eratosthenes的筛子非常快,但它需要O(n)空间.通过在连续的段中进行筛分,可以将筛分质子的O(sqrt(n))减少到比特阵列的O(1).在第一段,计算该段内每个筛分素数的最小倍数,然后以正常方式将筛分素数的倍数标记为复合物; 当所有筛选质数都被使用时,该段中剩余的未标记数字是素数.然后,对于下一个段,每个筛分素数的最小倍数是结束先前段中的筛分的倍数,因此筛分继续直到完成.
考虑从20到200的分段中筛分的示例.五个筛分质数分别为3,5,7,11和13.在100到120的第一个分段中,比特阵列有10个槽,槽0对应于101 ,插槽k对应100 + 2k + 1,插槽9对应119.该段中3的最小倍数为105,对应插槽2; 时隙2 + 3 = 5和5 + 3 = 8也是3的倍数.5的最小倍数在时隙2是105,而时隙2 + 5 = 7也是5的倍数.7的最小倍数是105在插槽2处,插槽2 + 7 = 9也是7的倍数.依此类推.
函数primesRange接受参数lo,hi和delta; lo和hi必须是偶数,lo <hi,lo必须大于sqrt(hi).分段大小是两倍增量.Ps是一个链表,其中包含小于sqrt(hi)的筛分素数,由于偶数被忽略,因此删除了2.Qs是链接列表,其包含进入相应筛分素数的当前片段中的最小倍数的筛子阵列的offest.在每个段之后,lo前进两次delta,因此对应于sier bitarray的索引i的数字是lo + 2i + 1.
function primesRange(lo, hi, delta)
function qInit(p)
return (-1/2 * (lo + p + 1)) % p
function qReset(p, q)
return (q - delta) % p
sieve := makeArray(0..delta-1)
ps := tail(primes(sqrt(hi)))
qs := map(qInit, ps)
while lo < hi
for i from 0 to delta-1
sieve[i] := True
for p,q in ps,qs
for i from q to delta step p
sieve[i] := False
qs := map(qReset, ps, qs)
for i,t from 0,lo+1 to delta-1,hi step 1,2
if sieve[i]
output t
lo := lo + 2 * delta
当被称为primesRange(100,200,10)时,筛分素数ps为[3,5,7,11,13]; qs最初是[2,2,2,10,8],对应于最小的倍数105,105,105,121和117,并且对于第二段重置为[1,2,6,0,11],对应于最小的倍数123,125,133,121和143.
你可以在这里看到这个程序 http://ideone.com/iHYr1f.除了上面显示的链接,如果你对使用素数进行编程感兴趣,我谦虚地在我的博客上推荐这篇文章.
有一个基于优先级队列的 Sieve 版本，可以根据您的要求产生尽可能多的质数，而不是所有质数都达到上限。它在经典论文“Eratosthenes 的真正筛选”和谷歌搜索“埃拉托色尼优先队列的筛选”中讨论过，在各种编程语言中出现了很多实现。
小智 5
只是我们正在用我们拥有的筛子进行分段。基本思想是假设我们必须找出 85 到 100 之间的素数。我们必须应用传统的筛法，但采用如下所述的方式：
所以我们取第一个素数 2 ，将起始数除以 2(85/2) 并将四舍五入到更小的数我们得到 p=42，现在再次乘以 2 我们得到 p=84，从这里开始加 2直到最后一个数字。所以我们所做的是我们已经删除了范围内 2(86,88,90,92,94,96,98,100) 的所有因子。
我们取下一个质数 3 ，将起始数除以 3(85/3) 并将四舍五入到较小的数我们得到 p=28，现在再次乘以 3 我们得到 p=84，从这里开始加 3 直到最后一个数字。所以我们所做的是删除了范围内3（87,90,93,96,99）的所有因子。
取下一个质数=5 ....... 继续做上面的步骤，你可以得到质数(2,3,5,7, ...) 通过使用传统的筛分高达 sqrt(n)。然后将其用于分段筛分。