筛选素数高达10 ^ 12

Question

我正在研究一些需要我生成高达10 ^ 12的所有素数的东西.

因为我以前从来没有需要这么多的素数,我通常只是实现该算法在这个网页在这里

当然,这里的问题是10 ^ 12大于整数的最大值,因此我无法生成该大小的数组.

我不熟悉用来有效生成这么多素数的方法,并且想知道是否有人能够对这种情况有所了解.

Answer 1

您将需要使用分段筛.

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

考虑从20到200的段中筛选100到200的示例; 5个筛分质数分别为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的倍数.依此类推.

函数素数采用参数lo,hi和delta; lo和hi必须是偶数,lo <hi,lo必须大于hi的平方根.分段大小是两倍增量.长度为m的数组ps包含小于hi的平方根的筛分素数,由于偶数数被忽略而被删除,由正常的Eratosthenes筛选计算得出.数组qs包含相应筛分素数的当前片段中最小倍数的筛子比特阵列的偏移量.在每个段之后,lo前进两次delta,因此对应于sier bitarray的索引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的价值至关重要; 为了速度,你应该使delta尽可能大,以便它适合高速缓冲存储器.使用您的语言库进行比特阵列,这样您只需为每个筛选位置取一个位.如果您需要一个简单的Eratosthenes筛子来计算筛分质数,这是我最喜欢的:

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.伪代码表示输出的地方你可以打印素数,或者在数组中收集素数,无论你想用它们做什么.

我在我的博客上做了很多关于素数的工作,包括在Prime页面上编写的包含分段筛的文章.