求所有小于200万素数的和需要多少时间？

我试图解决这个问题欧拉计划问题。我用java实现了欧拉筛作为辅助类。它对于小数字来说非常有效。但是当我输入 200 万作为限制时，它不会返回答案。我使用 Netbeans IDE。有一次我等了好几个小时，还是没有打印出答案。当我停止运行代码时，它给出了以下结果

Java 结果：2147483647
建造 成功（总时间：2,097 分钟 43秒）

这个答案是不正确的。即使等了这么久，这也是不正确的。虽然相同的代码会返回较小限制的正确答案。

欧拉筛法在本文底部给出了一个非常简单的算法page.

我的实现是这样的：

package support;

import java.util.ArrayList;
import java.util.List;

/**
 *
 * @author admin
 */
public class SieveOfEuler {
    int upperLimit;
    List<Integer> primeNumbers;

    public SieveOfEuler(int upperLimit){
        this.upperLimit = upperLimit;
        primeNumbers = new ArrayList<Integer>();
        for(int i = 2 ; i <= upperLimit ; i++)
            primeNumbers.add(i);
        generatePrimes();
    }

    private void generatePrimes(){
        int currentPrimeIndex = 0;
        int currentPrime = 2;
        while(currentPrime <= Math.sqrt(upperLimit)){
            ArrayList<Integer> toBeRemoved = new ArrayList<Integer>();
            for(int i = currentPrimeIndex ; i < primeNumbers.size() ; i++){
                int multiplier = primeNumbers.get(i);
                toBeRemoved.add(currentPrime * multiplier);
            }

            for(Integer i : toBeRemoved){
                primeNumbers.remove(i);
            }

            currentPrimeIndex++;
            currentPrime = primeNumbers.get(currentPrimeIndex);
        }
    }

    public List getPrimes(){
        return primeNumbers;
    }

    public void displayPrimes(){
        for(double i : primeNumbers)
            System.out.println(i);
    }
}

我很困惑！我的问题是

1）为什么要花这么多时间？我正在做的事情有什么问题吗？

如果您发现有问题，请提出改进​​我的编码风格的方法。

问题更新：

这是代码，我在其中计算计算出的素数的总和：

package projecteuler;

import java.io.IOException;
import java.math.BigInteger;
import java.util.ArrayList;
import java.util.logging.Level;
import java.util.logging.Logger;
import support.SieveOfEuler;

/**
 *
 * @author admin
 */
public class Problem10 {
    private int upperLimit;
    private BigInteger sumOfPrimes;
    public void getInput() {
        try {
            System.out.println("Enter the upper limit");
            upperLimit = Integer.parseInt(br.readLine());
        } catch (IOException ex) {
            Logger.getLogger(Problem10.class.getName()).log(Level.SEVERE, null, ex);
        }
    }

    public void execute() {
        BigInteger sum = new BigInteger("0");
        SieveOfEuler soe = new SieveOfEuler(upperLimit);
        ArrayList<Integer> primeNumbers = (ArrayList<Integer>)soe.getPrimes();
        for(int i : primeNumbers){
            sum = sum.add(new BigInteger(Integer.toString(i))) ;
        }
        System.out.println(sum);
    }

    public void printOutput() {
       //System.out.println(sumOfPrimes);
    } 
}

你的 Sieve 如此慢的原因是你犯了一个根本性的错误。这primeNumbers应该是布尔数组，而不是List。当你完成后，价值primeMumbers[i]将true对于素数和false对于复合材料。

这就是为什么它会产生如此大的差异：

• 设置或清除数组中的标志是O(1);即每次操作的小常数时间。
• 从 a 中删除一个元素ArrayList is O(N) where N是列表的大小...并且很大.
• Each ArrayList.remove(...)操作必须search列表。如果该值不再存在（因为您已经删除了它），则删除操作必须查看every列表中的剩余元素...最多约 200 万个...每次调用时。
• When ArrayList.remove(...)找到一个元素，它通过复制后备数组中左侧索引后的所有剩余元素来删除该元素。同样，每次删除一个条目时，您都会复制大约 200 万个条目。

我希望一个实施良好的埃拉托色尼筛法能够在几秒钟内计算出所有小于 200 万的素数。