java - “是素数”算法运行时

Question

我正在尝试制作最快的算法来确定一个数字是否为素数。我正在为从 3 到 100,000 的每个数字执行此操作。

   for(int i = 3; i < 100000; i += 1)
        if(isPrime(i))
            System.out.println(i);

它需要0.52秒。我的朋友建议不要迭代偶数：

for(int i = 3; i < 100000; i += 2)
        if(isPrime(i))
            System.out.println(i);

它需要 0.53 秒（可能是随机差异）。

为什么他的建议不减少运行时间？如果我遍历更少的数字，我希望程序运行得更快。

isPrime() 的代码：

public static boolean isPrime(int n)
{
    if((n % 2 == 0 && n != 2) || (n % 3 == 0  && n != 3)|| (n % 5 == 0 && n != 5))
        return false;
    for(int i = 5; i < n / 5; i += 2)
    {
        if(n % i == 0)
            return false;
    }
    return true;
}

score 9 · Accepted Answer

Most probably the bulk of the time is needed for printing out the primes to the console. Thus reducing the numbers tested won't notably affect the speed of the program, if the number of primes is not reduced as well.

Try to collect the primes into a string and print that out once, like this:

StringBuilder b = new StringBuilder();
for(int i = 3; i < 100000; i += 1)
    if(isPrime(i))
      b.append(i).append("\n");

System.out.println(b.toString());

score 4 · Accepted Answer

除了算法问题之外，您的瓶颈很可能是写入System.out流。这是一项耗时的任务，我认为您应该将该部分排除在基准循环之外。要快速测试这一点，只需将其注释掉（使用相应的if语句）：

int iterations=100000;
long time = System.nanoTime();
for(int i = 3; i < 100000; i += 2) { //notice: always use curly brackets!!!
    isPrime(i);
}
long endTime = System.nanoTime();
System.out.println("Time to go through " + iterations + " iterations: " + (endTime>time?endTime-time:endTime+time));
//notice: nanoTime might turn around, resulting in smaller (negative) endTime value

此外，Thomas 的回答对这个问题更加详细System.out.print，并且还提供了连接大量字符串的适当方法。

算法问题：

如果您使用 Erastothenes 筛法，那么在搜索下一个质数时，您已经找到了所有较小的质数。所以你应该存储它们，而不是检查每个大于 5 的奇数，你只需要检查你已经拥有的那些。

此外，同时，您不必检查所有这些，只需检查小于或等于您的数字平方根的那些：

//suppose we have a List<Integer> primeList (populated by previous execution loops)
// and Integer numberTested as the number under testing

for(int i=0; i<primeList.size();i++) {
    if(numberTested%primeList.get(i)==0) {
        //divider found, not prime
        break;
    }        

    if(primeList.get(i)>Math.sqrt(numberTested)) {
        //still not found a divider -- we found a prime
        primeList.add(numberTested);
        break;
    }
}

这有什么问题？Math.sqrt是一项昂贵的操作。比乘法成本高得多...因此，如果数字范围允许（您必须始终牢记这一点！），我们可以使用乘法来更快地进行比较：

sqrt(a)>b === a*a>b假设 a 和 b 都是正整数。

    Integer currentPrimeSquare = primeList.get(i)*primeList.get(i);
    if(currentPrimeSquare>numberTested) {
        //still not found a divider -- we found a prime
        primeList.add(numberTested);
        break;
    }

为了进一步调整这个，你也可以存储素数的平方——假设你有足够的内存......

score 1 · Accepted Answer

在比较 java 运行时时，需要担心 VM 本身的开销（例如，println 在每次执行时可能需要不同的时间）。要获得正确的运行时间比较，请将每个运行时间运行一千次并获取平均值以获得更准确的结果。

此外，在 Java 中实现Erastothenes 筛法并不难，而且会很快得到结果，尽管它会使用更多内存。

score 0 · Accepted Answer

1）您是否考虑过使用埃拉托色尼筛法来寻找素数？

2）你不应该用运行时间来衡量效率

3）您的 if 语句是素数，如果您正在检查n = {2,3,5}使用它来返回结果，这将阻止您执行其余代码（在这种情况下不会节省太多时间）

4）你的for循环，你可以从7（你已经检查过5的条件，6不是素数）到sqrt（n）

score 0 · Accepted Answer

如果您对迄今为止已知的最有效算法感兴趣，那么您应该考虑阅读AKS primality test，它在多对数时间内运行。

（这个答案基本上是对有关素性检验的问题的另一个答案的重申。）

score -2 · Accepted Answer

Maybe this article can help you:

boolean isPrime(int n) {
//check if n is a multiple of 2
if (n%2==0) return false;
//if not, then just check the odds
for(int i=3;i*i<=n;i+=2) {
    if(n%i==0)
        return false;
}
return true;
}

java - “是素数”算法运行时

6 回答 6

Related

Reference