在最短的时间内找到素数列表

Question

我读了很多算法来找到素数,结论是如果数不能被前面的任何素数整除,那么数就是素数.

我无法找到更准确的定义.基于此,我编写了一个代码并且它表现令人满意,直到我传递的最大数量为1000000.但我相信有更快的算法来找到比给定数字更小的所有素数.

以下是我的代码,我可以有更好的版本吗？

 public static void main(String[] args) {
    for (int i = 2; i < 100000; i++) {
        if (checkMod(i)) {
            primes.add(i);
        }
    }
}

private static boolean checkMod( int num) {
    for (int i : primes){
        if( num % i == 0){
            return false;
        }
    }
    return true;
}

Answer 1

你的素性测试中的好处是你只能按素数划分.

private static boolean checkMod( int num) {
    for (int i : primes){
        if( num % i == 0){
            return false;
        }
    }
    return true;
}

不好的是,你除以迄今为止发现的所有素数,也就是说,所有素数都小于候选者.这意味着对于低于一百万的最大素数999983,你除以78497个素数以发现这个数字是素数.这是很多工作.事实上,在这个算法中花费在素数上的工作占了所有工作的大约99.9%,当达到一百万时,更大的部分用于更高的限制.并且该算法几乎是二次的,要以n这种方式找到素数,你需要执行

n² / (2*(log n)²)

分歧.

一个简单的改进是提前停止分裂.让n是复合数目(即数量greter大于1,其具有比图1和其他除数n),并让d是的除数n.

现在,d为的除数n装置,其n/d是一个整数,并且还的除数n:n/(n/d) = d.所以我们可以自然地将除数n分成对,每个除数d产生对(d, n/d).

对于这样一对,有两种可能性:

1. d = n/d,意思是n = d²,或d = ?n.
2. 比如,两者是不同的,然后其中一个比另一个小d < n/d.但那立即转化为d² < n或d < ?n.

因此,无论哪种方式,每对除数都包含(至少)一个除数?n,因此,如果n是复数,则其最小除数(除1之外)不超过?n.

因此,当我们到达时,我们可以停止试验部门?n:

private static boolean checkMod( int num) {
    for (int i : primes){
        if (i*i > n){
            // We have not found a divisor less than ?n, so it's a prime
            return true;
        }
        if( num % i == 0){
            return false;
        }
    }
    return true;
}

注意:这取决于按升序迭代的素数列表.如果语言无法保证这一点,则必须使用不同的方法,通过索引ArrayList或类似的方式迭代.

在候选人的平方根处停止试验部门,对于低于一百万的最大素数999983,我们现在只需要将其除以1000以下的168个素数.这比以前少得多.在平方根处停止试验分裂,并且只用素数除法,就像试验分裂可能得到并要求一样好

2*n^1.5 / (3*(log n)²)

分裂,因为n = 1000000,这是一个大约750的因素,不错,是吗？

但这仍然不是很有效,找到下面所有质数的最有效方法n是筛子.易于实施的是经典的Eratosthenes筛.n在O(n*log log n)运算中找到下面的素数,有一些增强(预先考虑几个小素数的倍数),其复杂度可以减少到O(n)运算.具有更好渐近行为的相对较新的筛子是Atkin的Sieve,它n在O(n)操作中找到素数,或者在O(n/log log n)操作中增强消除一些小素数的倍数.Atkin的筛选实施起来更加复杂,因此Eratosthenes筛选的良好实施可能比天然的Atve筛选实施得更好.对于类似优化级别的实现,性能差异很小,除非限制变大(大于10 ¹⁰ ;并且实际上,由于更好的内存访问,Eratosthenes的Sieve比Siekin of Atkin更好地扩展的情况并不罕见模式).因此,我建议从Eratosthenes筛选开始,只有在优化的诚实努力下,它的表现不尽如人意,才能深入研究阿特金筛选.或者,如果您不想自己实现它,请找一个其他人已经认真调整过的好实现.

我在一个稍微不同的设置的答案中进入了更多细节,其中问题是找到第n个素数.一些或多或少有效方法的实现与该答案相关联,特别是一个或两个可用(但不是很优化)的Eratosthenes筛选实施方案.