素数计算乐趣

我们在工作中玩得很开心。这一切都始于其中一个人设置了Hackintosh，我们想知道它是否比我们拥有的（几乎）相同规格的Windows Box更快。所以我们决定为它写一个小测试。只是一个简单的素数计算器。它是用Java编写的，告诉我们计算前n个质数所需的时间。

下面的优化版本 - 现在需要约6.6秒

public class Primes {

    public static void main(String[] args) {
        int topPrime = 150000;
        int current = 2;
        int count = 0;
        int lastPrime = 2;

        long start = System.currentTimeMillis();

        while (count < topPrime) {

            boolean prime = true;

            int top = (int)Math.sqrt(current) + 1;

            for (int i = 2; i < top; i++) {
                if (current % i == 0) {
                    prime = false;
                    break;
                }
            }

            if (prime) {
                count++;
                lastPrime = current;
            }
            if (current == 2) {
             current++;
            } else {
                current = current + 2;
            }
        }

        System.out.println("Last prime = " + lastPrime);
        System.out.println("Total time = " + (double)(System.currentTimeMillis() - start) / 1000);
    } 
}

我们几乎已经失去了整个Hackintosh vs PC的情节，只是在优化它时玩得开心。第一次没有优化的尝试（上面的代码有几个）运行了大约52.6分钟，以找到前150000个素数。此优化运行时间约为 47.2 分钟。

如果你想尝试并发布你的结果，那就坚持下去。

我正在运行的PC的规格是奔腾D 2.8GHz，2GB RAM，运行Ubuntu 8.04。

到目前为止，最佳优化一直是电流的平方根，由Jason Z首次提及。