素数计算的乐趣 [英] Prime number calculation fun

问题描述

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

We're having a bit of fun here at work. It all started with one of the guys setting up a Hackintosh and we were wondering whether it was faster than a Windows Box of (nearly) same specs that we have. So we decided to write a little test for it. Just a simple Prime number calculator. It's written in Java and tells us the time it takes to calculate the first n Prime numbers.

下面的优化版本 - 现在需要~6.6secs

Optimised version below - now takes ~6.6secs

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分钟。

We've pretty much lost the plot of the whole Hackintosh vs PC thing and are just having some fun with optimising it. First attempt with no optimisations (the above code has a couple) ran around 52.6min to find the first 150000 prime numbers. This optimisation is running around 47.2mins.

如果您想要发布并发布结果，请坚持下去。

If you want to have a go and post your results, then stick em up.

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

Specs for the PC I'm running it on are Pentium D 2.8GHz, 2GB RAM, running Ubuntu 8.04.

目前为止的最佳优化一直是当前的平方根，最初由Jason Z提到。

推荐答案

嗯，我看到了几个快速的可以完成的优化。
首先，您不必尝试每个数字，最多只需要当前数字的一半。

Well I see a couple of quick optimizations that can be done. First you don't have to try each number up to half of the current number.

相反，您只需要尝试当前的平方根数字。

Instead you only have try up to the square root of the current number.

其他优化是BP所说的扭曲：
而不是

And the other optimization was what BP said with a twist: Instead of

int count = 0;
...
for (int i = 2; i < top; i++)
...
if (current == 2)
  current++;
else
  current += 2;

使用

int count = 1;
...
for (int i = 3; i < top; i += 2)
...
current += 2;

这应该可以加快速度。

编辑：

更多优化由Joe Pineda提供：

删除变量top。

More optimization courtesy of Joe Pineda:
Remove the variable "top".

int count = 1;
...
for (int i = 3; i*i <= current; i += 2)
...
current += 2;

如果这个优化确实增加速度取决于java。

计算平方与两个数相乘相比，root需要花费大量时间。但是，由于我们将乘法移动到for循环中，因此每个循环都会执行此操作。因此，这可能会降低速度，具体取决于java中的平方根算法的速度。

If this optimization indeed increases speed is up to java.
Calculating the square root takes a lot of time compared to multiplying two numbers. However since we move the multiplication into the for loop this is done every single loop. So this COULD slow things down depending on how fast the square root algorithm in java is.

这篇关于素数计算的乐趣的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！