素数计算的乐趣

Question

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

下面的优化版本 - 现在需要~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与PC之间的关系,并且只是在优化它时获得了一些乐趣.没有优化的第一次尝试(上面的代码有一对)跑了大约52.6分钟找到第一个150000素数.此优化运行大约47.2分钟.

如果您想要发布并发布结果,那么请坚持下去.

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

到目前为止,最佳优化是当前的平方根,由Jason Z首先提到.

Answer 1

这比1986年左右的8Mhz 8088涡轮帕斯卡筛的情况要差一些.但那是在优化之后:)

Answer 2

由于您是按升序搜索它们,因此您可以保留已经找到的素数列表,并仅检查它们的可分性,因为所有非素数都可以简化为较小的素数因子列表.将其与前一个提示相结合,不检查当前数字的平方根上的因子,您将拥有一个非常有效的实现.

Answer 3

好吧,我看到了几个可以做的快速优化.首先,您不必尝试每个数字,最多可达当前数字的一半.

相反,您只能尝试当前数字的平方根.

另一个优化是BP所说的扭曲:而不是

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".

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

如果这种优化确实增加了速度,那就是java.
与乘以两个数字相比,计算平方根需要花费大量时间.但是,由于我们将乘法移动到for循环中,因此每个循环都会执行此操作.因此,这可能会降低速度,具体取决于java中的平方根算法的速度.

Answer 4

这是一个快速而简单的解决方案:

• 找到低于100000的素数; 在5毫秒内发现9592
• 寻找低于1000000的素数; 在20毫秒内发现78498
• 寻找小于10000000的素数; 在143毫秒内发现664579
• 寻找低于1亿的素数; 在2024毫秒时发现了5761455

• 寻找低于10亿的素数; 50847534在23839 ms内被发现

  //returns number of primes less than n
  private static int getNumberOfPrimes(final int n)
  {
      if(n < 2) 
          return 0;
      BitSet candidates = new BitSet(n - 1);
      candidates.set(0, false);
      candidates.set(1, false);
      candidates.set(2, n);
      for(int i = 2; i < n; i++)
          if(candidates.get(i))
              for(int j = i + i; j < n; j += i)
                  if(candidates.get(j) && j % i == 0)
                      candidates.set(j, false);            
      return candidates.cardinality();
  }