java - 质数计算乐趣

Question

我们的工作很有趣。这一切都始于其中一个设置 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 规范是 Pentium D 2.8GHz，2GB RAM，运行 Ubuntu 8.04。

迄今为止最佳优化是当前的平方根，由 Jason Z 首次提及。

Answer 1

这比我在 1986 年左右在涡轮帕斯卡 8 Mhz 8088 上做的筛子要差一点。但那是在优化之后:)