找到少于200万的所有素数之和需要多长时间？
我试图解决这个项目欧拉问题 。 我将euler的筛子作为java中的辅助类实现。 它适用于小数字。 但是，当我输入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 primeNumbers; public SieveOfEuler(int upperLimit){ this.upperLimit = upperLimit; primeNumbers = new ArrayList(); 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 toBeRemoved = new ArrayList(); 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 primeNumbers = (ArrayList)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); 即每次操作的恒定时间很短。 - 从
ArrayList删除元素是O(N)，其中N是列表的大小……并且非常大 。 - 每个
ArrayList.remove(...)操作都必须搜索列表。 如果该值不再存在（因为您已经删除了它），则删除操作必须查看列表中的每个剩余元素……每次调用时最多约200万个… …每次调用它时。 - 当
ArrayList.remove(...)找到一个元素时，它会通过将元素一个索引之后的所有剩余元素复制到支持数组中的左侧来删除它。 同样，每次删除一个条目时，您最多可复制约200万个条目。
我希望一个实施良好的Erasothenes筛子能够在几秒钟内计算出不到200万的所有素数。
为了回答本主题标题中的问题：这是项目Euler网站所说的： http ： //projecteuler.net/index.php？section = about
我已经编写了我的程序但是需要几天才能得到答案吗？ 绝对不！ 每个问题都是根据“一分钟规则”设计的 ，这意味着尽管设计一个成功的算法可能需要几个小时才能解决更加困难的问题，但是有效的实施将允许在适当的计算机上获得解决方案。不到一分钟。
😉
for(int i = currentPrimeIndex ; i < primeNumbers.size() ; i++){ int multiplier = primeNumbers.get(i); toBeRemoved.add(currentPrime * multiplier); }
在第一步，这将生成一个200万倍的2的ArrayList（toBeRemoved）。
然后它迭代到BeRemoved，为toBeRemoved中的每个条目扫描一次200万个候选素数的整个数组 。 toBeRemoved中的一半值不可能是primeNumbers因为它们太大了。 每次删除都会导致每个值的索引大于删除的索引，并向下移动一个位置。
我认为这是效率低下的主要原因。 实现Eratosthenes筛子的通常方法是创建一个包含200万个布尔值的数组，最初都是真的。 当i被确定为非素数时，将possibly_prime[i]设置为false。 要查找下一个素数，请向前扫描以查找true值。 要获得最后所有素数的列表，请迭代记录每个true值的索引的数组。 你应该为欧拉的筛子做同样的事情。
对于高达200万的素数，您将无需优化。
一些明显的错误：
while(currentPrime <= Math.sqrt(upperLimit))
每个步骤都计算平方根（除非编译器优化）。 您应该计算一次并存储结果。
currentPrimeIndex++;
你应该至少做出明显的优化，只测试奇数。 你已经知道偶数不是素数。 这应该把你的时间缩短一半。
此外，您正在使用powershell方法来查找素数。 对于较大的上限，这将是缓慢的。 您应该为搜索使用更好的算法 - 您将能够在网络中找到更多信息，但我不知道是否允许这是项目欧拉的精神。
import java.util.*; public class PrimeSum { public static int isPrime(int num) { int sum = 0; int factor = 1; while(factor <= num) { if(num % factor != 0) { sum += factor; factor ++; } else { factor ++; } } return sum; } public static void main(String[] args) { System.out.println("The program gets the sum of all prime numbers."); Scanner scan = new Scanner(System.in); System.out.print("Enter a number: "); int num = scan.nextInt(); int sum = isPrime(num); System.out.println(sum); } }
while（currentPrime <= Math.sqrt（upperLimit））//它降低了复杂性，并且总和不是int的另一点。 溢出发生
如果它可以帮助您查看我的解决方案。 这是我的解决方案
public static boolean isPrime(int i) { // general isPrime method if (i < 2) { return false; } else if (i % 2 == 0 && i != 2) { return false; } else { for (int j = 3; j <= Math.sqrt(i); j = j + 2) { if (i % j == 0) { return false; } } } return true; } public static boolean isPrimeForOdd(int i){ // only for odds for (int j = 3; j <= Math.sqrt(i); j = j + 2) { if (i % j == 0) { return false; } } return true; } public static long sumOfPrimes(int n) { long sum = 2; for (int i = 3; i < n; i += 2) { if (isPrimeForOdd(i)) { sum += i; } } return sum; } public static void main(String[] args) throws ParseException { System.out.println(sumOfPrimes(2000000)); }
-
列表是正确的类型吗？ 在
remove(obj)期间，Set会表现得更好。 在您的情况下，尝试一个BitSet。 -
首先创建一个（长）要删除的元素列表，然后单独删除它们。 为什么不简单地删除它们？
-
结果不适合
int。
即使没有筛子，这个问题也可以在不到1秒的时间内解决。 检查数字是否为素数： http ： //www.parseexception.com/how-to-check-whether-a-number-is-prime-or-not/
对所有数字执行此操作并将它们相加。
这是一个使用简单的Eratosthenes筛子的解决方案：
function sumPrimes(n) sum, sieve := 0, makeArray(2..n, True) for p from 2 to n if sieve[p] sum := sum + p for i from p*p to n step p sieve[i] := False return sum
我在这里用Python编写这个解决方案，需要一秒钟的时间。 如果你对素数编程感兴趣，我谦虚地在我的博客上推荐这篇文章 。