algorithm - Eratosthenes 的分段筛？

Question

制作一个简单的筛子很容易:

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)怎么办？

Answer 1

分段筛的基本思想是选择小于 n 平方根的筛分素数，选择适合内存的相当大的段大小，然后对每个段进行筛分反过来，从最小的开始。在第一段，计算段内每个筛素的最小倍数，然后按常规方式将筛素的倍数标记为复合；当所有的筛选素数都用完后，该段中剩余的未标记数为素数。然后，对于下一个片段，对于每个筛分素数，您已经知道当前片段中的第一个倍数(它是结束前一个片段中该素数筛分的倍数)，因此您对每个筛分素数进行筛分，依此类推直到你完成。

n 的大小无关紧要，除了较大的 n 比较小的 n 需要更长的筛选时间；重要的是段的大小，它应该尽可能大(例如，机器上主内存缓存的大小)。

您可以看到分段筛的简单实现 here .请注意，分段筛比另一个答案中提到的奥尼尔的优先级队列筛要快得多；如果你有兴趣，这里有一个实现 here .

编辑:我写这个是为了不同的目的，但我会在这里展示它，因为它可能有用:

尽管 Eratosthenes 筛法非常快，但它需要 O(n) 空间。通过在连续的段中执行筛分，可以将筛素数的 O(sqrt(n)) 减少到位数组的 O(1)。第一段，计算段内各筛质数的最小倍数，然后按正常方式将筛质数的倍数标为合；当所有的筛选素数都用完后，该段中剩余的未标记数为素数。然后，对于下一段，每个筛分质数的最小倍数是前一段结束筛分的倍数，如此继续筛分直到结束。

考虑筛分从 100 到 200 的例子，每个筛分 20。五个筛分素数是 3、5、7、11 和 13。在第一个从 100 到 120 的分片中，位数组有十个槽，槽 0对应101，slot k对应100+2k+1，slot 9对应119。段中3的最小倍数为105，对应slot 2； slot 2+3=5 and 5+3=8 也是3的倍数，5的最小倍数在slot 2是105，slot 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，因此筛位数组的索引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 .除了上面显示的链接之外，如果您对使用质数进行编程感兴趣，我谦虚地推荐这个 essay在我的博客上。