java素数计算乐趣

Question

我们在这里工作很开心。这一切都始于其中一个家伙安装了一个黑客软件，我们想知道它是否比我们拥有的（几乎）相同规格的Windows设备更快。所以我们决定为它写一个小测试。只是一个简单的素数计算器。它是用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的规格是奔腾D2.8GHz，2GB内存，运行Ubuntu 8.04

迄今为止最好的优化方法是电流的平方根，Jason Z首先提到了这一点。

Answer 1

我看到了一些可以快速完成的优化。 首先，你不必尝试每一个数字，最多是当前数字的一半

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

另一个优化是英国石油公司说的话，有点曲折： 而不是

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 2

在C#中：

class Program
{
    static void Main(string[] args)
    {
        int count = 0;
        int max = 150000;
        int i = 2;

        DateTime start = DateTime.Now;
        while (count < max)
        {
            if (IsPrime(i))
            {
                count++;
            }

            i++;

        }
        DateTime end = DateTime.Now;

        Console.WriteLine("Total time taken: " + (end - start).TotalSeconds.ToString() + " seconds");
        Console.ReadLine();
    }

    static bool IsPrime(int n)
    {
        if (n < 4)
            return true;
        if (n % 2 == 0)
            return false;

        int s = (int)Math.Sqrt(n);
        for (int i = 2; i <= s; i++)
            if (n % i == 0)
                return false;

        return true;
    }
}

输出：

总耗时：2.087秒

Answer 3

下面是一个快速而简单的解决方案：

• 寻找小于100000的素数；在5ms内发现9592个
• 发现素数小于1000000；在20毫秒内发现78498例
• 发现素数小于10000000；143 ms中发现664579例
• 寻找小于100000000的素数；2024年发现5761455例

• 寻找小于100000000的素数；在23839例ms中发现50847534例

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

Answer 4

这比1986年左右我在8兆赫8088涡轮帕斯卡上使用的筛子要差一点。但那是在优化之后：）