java - "is prime"算法运行时间

Question

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

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

它需要 0.52 秒。我的 friend 建议不要迭代偶数:

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

Answer 1

很可能大部分时间都需要将素数打印到控制台。因此，如果素数的数量没有减少，那么减少测试的数量不会显着影响程序的速度。

尝试将素数收集到一个字符串中并打印一次，如下所示:

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());