java - 筛选高达 10^12 的素数

Question

我正在做的事情要求我生成所有不超过 10^12 的素数。

因为我以前从来不需要这么多素数，所以我通常只是在这个网页上实现算法here

当然，这里的问题是 10^12 大于整数的最大值，因此我无法创建该大小的数组。

我不熟悉人们用来有效生成这么多素数的方法，想知道是否有人可以阐明这种情况。

Answer 1

您需要使用分段筛。

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

考虑以 20 为单位从 100 筛选到 200 的示例； 5个筛选素数分别为3、5、7、11、13。第一段100到120位数组有10个槽位，槽位0对应101，槽位k对应100+2k+1，槽位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的倍数，以此类推。

函数 primes 接受参数 lo、hi 和 delta； lo 和 hi 必须是偶数，其中 lo < hi，并且 lo 必须大于 hi 的平方根。段大小是增量的两倍。长度为 m 的数组 ps 包含小于 hi 平方根的筛选素数，由于忽略了偶数，因此删除了 2，这是通过正常的埃拉托色尼筛法计算的。数组 qs 包含当前段中相应筛选素数的最小倍数的筛选位数组的偏移量。每段后lo前进两倍delta，所以筛位数组的索引i对应的数为lo + 2 i + 1。

function primes(lo, hi, delta)
    sieve := makeArray(0..delta-1)
    ps := tail(primes(sqrt(hi)))
    m := length(ps)
    qs := makeArray(0..m-1)
    for i from 0 to m-1
        qs[i] := (-1/2 * (lo + ps[i] + 1)) % ps[i]
    while lo < hi
        for i from 0 to delta-1
            sieve[i] := True
        for i from 0 to m-1
            for j from qs[i] to delta step ps[i]
                sieve[j] := False
            qs[i] := (qs[i] - delta) % ps[i]
        for i from 0 to delta-1
            t := lo + 2*i + 1
            if sieve[i] and t < hi
                output t
        lo := lo + 2*delta

对于上面给出的示例，这称为素数 (100, 200, 10)。在上面给出的示例中，qs 最初是 [2,2,2,10,8]，对应于 105、105、105、121 和 117 的最小倍数，并且在第二段重置为 [1,2,6, 0,11]，对应最小的倍数123、125、133、121、143。

delta的值很关键；为了速度，您应该使增量尽可能大，只要它适合高速缓存。将您的语言库用于位数组，这样您只需为每个筛选位置取一个位。如果您需要一个简单的埃拉托色尼筛法来计算筛素数，这是我最喜欢的:

function primes(n)
    sieve := makeArray(2..n, True)
    for p from 2 to n step 1
        if sieve(p)
            output p
            for i from p * p to n step p
                sieve[i] := False

这些函数都是伪代码；您必须使用适当的整数数据类型转换为 Java。在伪代码表示输出的地方，您可以打印素数，或将素数收集在数组中，无论您想用它们做什么。

我在我的博客上做了很多关于质数的工作，包括论文 Programming with Prime Numbers其中包括最后一页上的分段筛子。