所有素数低于200万的总和

Question

项目欧拉的问题10:

该程序针对较小的数字运行,并且减速到数十万的爬行.在200万,即使程序看起来仍在运行,答案也无法显示.

我正在尝试实施Eratosthenes筛选.它应该非常快.我的做法有什么问题？

import java.util.ArrayList;

public class p010
{
  /**
   * The sum of the primes below 10 is 2 + 3 + 5 + 7 = 17
   * Find the sum of all the primes below two million.
   * @param args
   */
  public static void main(String[] args)
  {
    ArrayList<Integer> primes = new ArrayList<Integer>();
    int upper = 2000000;
    for (int i = 2; i < upper; i++)
    {
      primes.add(i);
    }
    int sum = 0;
    for (int i = 0; i < primes.size(); i++)
    {
      if (isPrime(primes.get(i)))
      {
        for (int k = 2; k*primes.get(i) < upper; k++)
        {
          if (primes.contains(k*primes.get(i)))
          {
            primes.remove(primes.indexOf(k*primes.get(i)));
          }
        }
      }
    }
    for (int i = 0; i < primes.size(); i++)
    {
      sum += primes.get(i);
    }
    System.out.println(sum);
  }

  public static boolean isPrime(int number)
  {
    boolean returnVal = true;
    for (int i = 2; i <= Math.sqrt(number); i ++)
    {
      if (number % i == 0)
      {
        returnVal = false;
      }
    }
    return returnVal;
  }

}

Answer 1

您似乎正在尝试实施Eratosthenes的Sieve,它应该表现得更好O(N^2)(事实上​​,维基百科说它是O(N log(log N))......).

根本问题是您选择的数据结构.你已经选择将剩余的主要候选人代表作为ArrayList素数.这意味着您的测试以查看数字是否仍在集合中需要O(N)进行比较... N其余是素数的剩余数量.然后你ArrayList.remove(int)用来删除非素数......这O(N)也是.

这一切都增加了让您的筛实现更糟比O(N^2).

解决方案是ArrayList<Integer>用数组boolean[]中的位置(索引)boolean表示数字的位置替换,布尔值表示数字是素数还是可能素数,或者不是素数.

^{(还有其他问题,我没有注意到......看到其他答案.)}