做一个简单的筛子很容易：
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）怎么办？
分段筛的基本思想是选择小于 n的 平方根的筛素数，选择仍然适合内存的较大段大小，然后依次从最小的段开始依次筛分每个段。在第一段，计算该段内每个筛素的最小倍数，然后以常规方式将筛素的倍数标记为复合。当使用所有筛选质数时，段中其余未标记的数字为质数。然后，对于下一个段，对于每个筛分质数，您已经知道当前段中的第一个倍数（是上一个段中对该质数的筛分结束的倍数），因此您可以对每个筛分质数进行筛分，依此类推直到完成为止。
n 的大小无关紧要，只是较大的 n 会比较小的 n 花费更长的时间进行筛选。重要的是段的大小，该段的大小应尽可能方便（例如，计算机上的主内存缓存的大小）。
您可以在此处看到分段筛的简单实现。请注意，分段筛将比另一个答案中提到的O’Neill优先级排队筛快得多。如果你有兴趣，有一个执行在这里。
编辑： 我写这是出于不同的目的，但我将在这里展示，因为它可能有用：
尽管Eratosthenes筛网非常快，但它需要O（n）空间。通过在连续段中执行筛选，可以将其减少到筛选质数的O（sqrt（n））加上位数组的O（1）。在第一段，计算该段内每个筛素的最小倍数，然后以常规方式将筛素的倍数标记为复合。当使用所有筛选质数时，段中其余未标记的数字为质数。然后，对于下一个分段，每个筛素的最小倍数是在上一个分段中结束筛分的倍数，因此筛分一直持续到完成。
考虑在20的段中从100到200的筛子的示例。五个筛素数为3、5、7、11和13。在从100到120的第一个段中，位阵列有10个插槽，插槽0对应于101 ，对应于100 + 2k + 1的插槽k和对应于119的插槽9。段中3的最小倍数是105，对应于插槽2；插槽2 + 3 = 5和5 + 3 = 8也是3的倍数。插槽2处5的最小倍数是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是一个链表，其中包含对应的筛选质数的当前片段中最小倍数的筛分位阵列中的最差位。在每个段之后，lo前进两次delta，因此对应于筛位数组索引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，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。并且除了上面显示的链接之外，如果您对使用质数编程感兴趣，我会在我的博客中适度推荐这篇文章。
