发现素数的在最短的时间列表 [英] Finding the list of prime numbers in shortest time

问题描述

我看了很多很多算法来找到素数，得出的结论是，一些是一个素数，如果它不是整除其任何preceding素数。

我不能够找到一个更precise定义。在此基础上我已经写了code和它执行令人满意，直到最大数我通过为1000000。但是我相信，有更快的算法来找到所有素数超过给定数量较少。

以下是我的code，我可以有相同的一个更好的版本？

 公共静态无效的主要（字串[] args）{
    的for（int i = 2; I＆LT; 100000;我++）{
        如果（checkMod（i））的{
            primes.add（ⅰ）;
        }
    }
}

私有静态布尔checkMod（INT NUM）{
    对于（INT I：素数）{
        如果（NUM％我== 0）{
            返回false;
        }
    }
    返回true;
}
 

解决方案

在您的素性测试的好处是，你只用素数除以。

 私有静态布尔checkMod（INT NUM）{
    对于（INT I：素数）{
        如果（NUM％我== 0）{
            返回false;
        }
    }
    返回true;
}
 

坏的事情是，你把通过的所有的素数，发现至今，即所有素数比候选人更小。这意味着，对于低于1百万的最大素，999983，您除以78497素数地发现，这个数字是一个素数。这是一个很大的工作。这么多，其实，这项工作在这个算法帐户要一百万，为更高的限制较大部分时花了素数约99.9％的工作。这算法几乎是二次，找到素数为 N 通过这种方式，你需要进行关于

 N²/（2 *（log n）的²）
 

师。

一个简单的改进是停止分裂较早。让 N 是一个合数（即小于1的数greter有除数不是1和 N ），并让 D 是一个除数 N 。

现在， D 是的 N 表示 N / D 是一个整数，并且还 N 的除数： N /（N / D）= D 。 因此，我们可以 N 成对，每个因子 D 引起的对<$ C $的自然组的除数C>（D，N / D）。

有关这样的一对，有两种可能性：

1. D = N / D ，这意味着 N =D²或 D = √N。
2. 在这两者是不同的，那么其中一个比另一个更小，说 D＆LT; N / D 。但是，马上转换为D²＆LT; ñ或 D＆LT; √N。

所以，无论哪种方式，每对除数包含（至少）一个不超过√N，因此，如果 N 是合数，它的最小除数（除了1以外）不超过√N

因此​​，我们可以在我们已经达到停止审判庭√N：

 私有静态布尔checkMod（INT NUM）{
    对于（INT I：素数）{
        如果（I * I将N）{
            //我们还没有找到一个除数比√N少，所以这是一个素数
            返回true;
        }
        如果（NUM％我== 0）{
            返回false;
        }
    }
    返回true;
}
 

注：这取决于素数被重复升序排列的名单上。如果不是由语言保证的，你必须通过的ArrayList 或类似的东西使用不同的方法，通过迭代指数。

停止审判庭在候选的平方根的最大素数低于1百万，999983，我们现在只需要通过以下1000 168的素数，这比$ P $工作少了很多pviously来划分的。停止审判庭的平方根，并且只能由素数划分，是不如审判庭所能得到的，需要约

  2 * N ^ 1.5 /（3 *（log n）的²）
 

师，为ň= 1000000 ，这是约750，不坏的一个因素，是吧？

但是，这仍然不是很有效，最快捷的方法来找到以下所有质数ñ的筛子。简单的实现是一个经典的的href="http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes">筛。这个发现以下 N 在O（N *日志log n）的操作，有一些增强（省去了几个小的素数在考虑提前倍数），其复杂性可能是素数降低到O（n）的操作。一个相对较新筛具有更好的渐近行为是筛，该发现的素数为ñ 在O（n）的操作，或者取消一些小的素数的倍数，在O（N / log日志N）业务的提升。 阿特金的筛是实现起来更复杂，所以它可能是一个很好的实现埃拉托色尼的筛的性能比一个天真的实现阿特金的筛更好。对于喜欢优化级别的实现，性能差异很小，除非极限变大（大于10 ¹⁰ ;并且它的情况并不少见，在实践中，埃拉托色尼的筛鳞比阿特金的筛超越更好即，由于更好的存储器访问模式）。因此，我建议开始与埃拉托色尼的筛，只有当它的表现并不理想，尽管在优化诚实的努力，钻研阿特金的筛。或者，如果你不想自己实现它，找到一个很好的实现别人已经严重关注。

我已经进入了在答案略有不同的设置，问题出在哪里被找到第n个素数。的更多或更少的有效方法的一些实现被从该应答的联系，特别是一个或两个可用的（虽然不多优化）埃拉托塞尼的筛。的实现

I read lot many algorithms to find prime numbers and the conclusion is that a number is a prime number if it is not divisible by any of its preceding prime numbers.

I am not able to find a more precise definition. Based on this I have written a code and it performs satisfactory till the max number I pass is 1000000. But I believe there are much faster algorithms to find all primes lesser than a given number.

Following is my code, can I have a better version of the same?

 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;
}

解决方案

The good thing in your primality test is that you only divide by primes.

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

The bad thing is that you divide by all primes found so far, that is, all primes smaller than the candidate. That means that for the largest prime below one million, 999983, you divide by 78497 primes to find out that this number is a prime. That's a lot of work. So much, in fact, that the work spent on primes in this algorithm accounts for about 99.9% of all work when going to one million, a larger part for higher limits. And that algorithm is nearly quadratic, to find the primes to n in this way, you need to perform about

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

divisions.

A simple improvement is to stop the division earlier. Let n be a composite number (i.e. a number greter than 1 that has divisors other than 1 and n), and let d be a divisor of n.

Now, d being a divisor of n means that n/d is an integer, and also a divisor of n: n/(n/d) = d. So we can naturally group the divisors of n into pairs, each divisor d gives rise to the pair (d, n/d).

For such a pair, there are two possibilities:

1. d = n/d, which means n = d², or d = √n.
2. The two are different, then one of them is smaller than the other, say d < n/d. But that immediately translates to d² < n or d < √n.

So, either way, each pair of divisors contains (at least) one not exceeding √n, hence, if n is a composite number, its smallest divisor (other than 1) does not exceed √n.

So we can stop the trial division when we've reached √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;
}

Note: That depends on the list of primes being iterated in ascending order. If that is not guaranteed by the language, you have to use a different method, iterate by index through an ArrayList or something like that.

Stopping the trial division at the square root of the candidate, for the largest prime below one million, 999983, we now only need to divide it by the 168 primes below 1000. That's a lot less work than previously. Stopping the trial division at the square root, and dividing only by primes, is as good as trial division can possibly get and requires about

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

divisions, for n = 1000000, that's a factor of about 750, not bad, is it?

But that's still not very efficient, the most efficient methods to find all primes below n are sieves. Simple to implement is the classical Sieve of Eratosthenes. That finds the primes below n in O(n*log log n) operations, with some enhancements (eliminating multiples of several small primes from consideration in advance), its complexity can be reduced to O(n) operations. A relatively new sieve with better asymptotic behaviour is the Sieve of Atkin, which finds the primes to n in O(n) operations, or with the enhancement of eliminating the multiples of some small primes, in O(n/log log n) operations. The Sieve of Atkin is more complicated to implement, so it's likely that a good implementation of a Sieve of Eratosthenes performs better than a naive implementation of a Sieve of Atkin. For implementations of like optimisation levels, the performance difference is small unless the limit becomes large (larger than 10¹⁰; and it's not uncommon that in practice, a Sieve of Eratosthenes scales better than a Sieve of Atkin beyond that, due to better memory access patterns). So I would recommend beginning with a Sieve of Eratosthenes, and only when its performance isn't satisfactory despite honest efforts at optimisation, delve into the Sieve of Atkin. Or, if you don't want to implement it yourself, find a good implementation somebody else has already seriously tuned.

I have gone into a bit more detail in an answer with a slightly different setting, where the problem was finding the n-th prime. Some implementations of more-or-less efficient methods are linked from that answer, in particular one or two usable (though not much optimised) implementations of a Sieve of Eratosthenes.

这篇关于发现素数的在最短的时间列表的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！