找到不到200万的所有素数之和需要多长时间？

Question

我试图解决这个项目欧拉问题.我实现了euler的筛子作为java中的帮助类.它适用于小数字.但是,当我输入200万作为限制时,它不会返回答案.我使用Netbeans IDE.我等了很多个小时一次,但仍然没有打印答案.当我停止运行代码时,它给出了以下结果

Java结果:2147483647
BUILD SUCCESSFUL(总时间:2,097分43秒)

这个答案是不正确的.即使等了这么多时间,这也是不正确的.虽然相同的代码返回较小限制的正确答案.

在这个页面的底部给出了一个非常简单的算法.

我的实现是这样的:

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

Answer 1

你的Sieve速度太慢的原因是你犯了一个根本性的错误.的primeNumbers应该是布尔值的阵列,而不是一个List.完成后,primeMumbers[i]将为true素数和false复合物的值.

这就是它产生如此巨大差异的原因:

• 设置或清除数组中的标志是O(1); 即每次操作的恒定时间很短.
• 从删除元素ArrayList是O(N)这里N是列表的大小...以及非常大.
• 每个ArrayList.remove(...)操作都必须搜索列表.如果该值不再存在(因为您已经删除了它),则删除操作必须查看列表中的每个剩余元素......每次调用时最多约200万个...每次调用它.
• 当ArrayList.remove(...)找到一个元素时,它会通过将元素一个索引之后的所有剩余元素复制到支持数组中的左侧来删除它.同样,每次删除一个条目时,您最多可复制约200万个条目.

我希望一个实施良好的Erasothenes筛子能够在几秒钟内计算出不到200万的所有素数.