How long does it take to find the sum of all primes less than 2 million?

Question

I tried to solve this Project Euler Question . I implemented an Euler sieve as a helper class in java. This is very suitable for small numbers. But when I enter 2 million as a limit, it does not return an answer. I am using the Netbeans IDE. I waited many hours, but he still did not print out the answer. When I stopped using the code, it gave the following result:

Java Result: 2147483647
BUILDING SUCCESSFUL (total time: 2097 minutes 43 seconds)

This answer is incorrect. Even after waiting so much time, this is not true. Although the same code returns the correct answers for less restrictions.

The Euler sieve has a very simple algorithm given on the botton of this page .

My implementation is as follows:

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

I'm confused! My questions

1) Why is it taking so long? Is there something wrong with what I'm doing?

Please suggest ways to improve your coding style if you find something is wrong.

Question updated:

Here is the code where I calculate the sum of the calculated primes:

 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

The reason your sieve is so slow is because you made a fundamental mistake. primeNumbers should be an array of booleans, not List . When you are done, the primeMumbers[i] value will be true for primes and false for composites.

This is why it matters a lot:

• Setting or clearing the flag in the O(1) array; that is, a small constant time for surgery.
• Removing an element from an ArrayList is O(N) , where N is the size of the list ... and very large.
• Each ArrayList.remove(...) operation must perform a list search. If the value no longer exists (since you already deleted it), the delete operation should look at every remaining item in the list ... up to ~ 2 million of them ... every time it is called.
• When ArrayList.remove(...) finds an element, it deletes it by copying all other elements after the element index to the left in the support array. Again, you copy up to ~ 2 million records ... every time you delete them.

I expect a well-made Erasothenes sieve to be able to calculate all primes of less than 2 million in a few seconds.

Answer 2

 for(int i = currentPrimeIndex ; i < primeNumbers.size() ; i++){ int multiplier = primeNumbers.get(i); toBeRemoved.add(currentPrime * multiplier); } 

In the first step, this generates an ArrayList of 2 million times 2 (toBeRemoved).

It then iterates over BeRemoved, looking at the entire array of 2 million possible primes once for each entry in toBeRemoved. Half of the values ​​in toBeRemoved cannot be in primeNumbers , because they are too large. Each deletion leads to each value with a higher index than the deleted one, moves down one place.

I think this is the main source of inefficiency. The usual way to implement the Eratosthenes sieve is to create an array of 2 million Boolean values, initially all true. When i defined as odd, set possibly_prime[i] to false. To find the next prime, scan ahead looking for true . To get a list of all prime numbers at the end, iterate through an array that writes the index of each true value. You have to do almost the same for Euler sieve.

You no longer need to optimize for primes up to 2 million.

Answer 3

To answer the question in this topic title: this is what the Euler project website says: http://projecteuler.net/index.php?section=about

I wrote my program, but does it take several days to answer the question? Absolutely not! Each problem was developed in accordance with the “one-minute rule” , which means that although it may take several hours to develop a successful algorithm with more complex problems, an effective implementation will solve the problems obtained on a computer with moderate power in less than a minute.

; -)

Answer 4

Some obvious errors:

 while(currentPrime <= Math.sqrt(upperLimit)) 

The square root is calculated at each step (if not optimized by the compiler). You must calculate it once and save the result.

 currentPrimeIndex++; 

You should at least do the obvious optimization and test the odd numbers. You already know that even numbers are not prime. This should cut the time by half.

In addition, you use brute force to find primes. This will be slow for large upper limits. You should use the best algorithm for your search - you can find more information on the Internet, but I do not know if this is permitted in the spirit of Project Euler.

Answer 5

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

Answer 6

while (currentPrime <= Math.sqrt (upperLimit)) // This reduces complexity and another point the sum is not int . overflow occurs

If this helps you take a look at my solution. Here is my solution

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

Answer 7

• Is the list suitable for this? During remove(obj) set will work much better. In your case, try BitSet .

• First you create a (long) list of items to delete, and then delete them separately. Why not just delete them?

• The result is not suitable for int .

Answer 8

Even without a sieve, this question can be resolved in less than 1 second of complexity. To check if a number is prime or not: http://www.parseexception.com/how-to-check-whether-a-number-is-prime-or-not/

Perform this operation for all numbers and sum them.

Answer 9

Here is a solution using a simple eratosthenes sieve:

 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 

I will encode this solution in Python here , where it takes one to a quarter seconds. If you are interested in programming with primes, I modestly recommend this essay on my blog.