我正在尝试解决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); } }
筛速如此之慢的原因是您犯了一个根本性的错误。的primeNumbers应该是布尔数组,而不是List。完成后,的值primeMumbers[i]将是true质数和false合成数。
primeNumbers
List
primeMumbers[i]
true
false
这就是为什么它会带来如此大的改变的原因:
O(1)
ArrayList
O(N)
N
ArrayList.remove(...)
我希望能很好地实施Erasothenes筛网,在几秒钟内就能计算出所有小于200万的素数。