埃拉托斯特尼的分段筛？

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

只是我们用现有的筛子进行分段。基本思想是我们必须找出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，依此类推…………继续执行上述步骤。你可以通过使用传统的sqrt（n）筛子得到素数（2,3,5,7，…）。然后将其用于分段筛。

Answer 2

有一种基于优先级队列的筛子，它能产生你所要求的那么多素数，而不是所有的素数都达到一个上限。在经典论文“厄拉多塞的真正筛子”中讨论过这个问题，在谷歌上搜索“埃拉托色尼优先队列的筛子”会出现很多不同编程语言的实现。

Answer 3

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

n的大小并不重要，只是较大的n比较小的n需要更长的时间来筛选；重要的大小是段的大小，它应该尽可能大（例如，机器上主内存缓存的大小）。

您可以在这里看到分段筛选的简单实现。请注意，分段筛选将比另一个答案中提到的O'Neill的优先级队列筛选快得多；如果您感兴趣，这里有一个实现。

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

虽然埃拉托斯特尼筛非常快，但它需要O（n）空间。对于筛选素数，这可以减少到O（sqrt（n）），而对于位数组，这可以通过在连续段中进行筛选来减少到O。在第一段，计算段内每个筛分底物的最小倍数，然后按正常方式将筛分底数的倍数标记为复合；当所有的筛选素数都被使用时，段中剩余的未标记数就是素数。然后，对于下一段，每个筛分素的最小倍数是前一段筛分结束的倍数，因此筛分一直持续到结束。

考虑从100到200的筛子以20为分段的例子。五个筛子质数是3、5、7、11和13。在从100到120的第一个分段中，位数组有十个槽，槽0对应101，槽k对应1002k1，槽9对应119。段中3的最小倍数是105，对应槽2；槽2 3=5和5 3=8也是3的倍数。5的最小倍数是槽2处的105，槽2 5=7也是5的倍数。7的最小倍数在槽2是105，槽2 7=9也是7的倍数。以此类推。

函数primesRange采用参数lo、hi和deltalo和hi必须是偶数，其中lo

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.除了上面显示的链接之外，如果你对素数编程感兴趣，我会在我的博客上html" target="_blank">推荐这篇文章。