一尘不染

找到所有小于200万的质数之和需要多少时间?

algorithm

我正在尝试解决Euler项目问题。我在Java中将euler的筛子实现为辅助类。对于少数人来说效果很好。但是,当我输入200万作为限制时,它不会返回答案。我使用Netbeans
IDE。我一次等了很多小时,但仍然没有打印出答案。当我停止运行代码时,它给出了以下结果

Java结果:2147483647
构建成功(总时间: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);
    } 
}

阅读 263

收藏
2020-07-28

共1个答案

一尘不染

筛速如此之慢的原因是您犯了一个根本性的错误。的primeNumbers应该是布尔数组,而不是List。完成后,的值primeMumbers[i]将是true质数和false合成数。

这就是为什么它会带来如此大的改变的原因:

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

我希望能很好地实施Erasothenes筛网,在几秒钟内就能计算出所有小于200万的素数。

2020-07-28