"是素数"算法运行时

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

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