I'm trying to find the sum of primes below 2 million in Java

Question

I'm trying to find the sum of primes below millions. My code works when I try to find the sum of primes below hundred thousands but when I go large numbers it doesn't work. So I need some help to get this work for big numbers...

import java.util.Scanner;
public class sumPrime {

  public static void main (String args []){

    long n = 2000000; int i; int j;int sum =0;
    for (i=2; i <n; i++){
        for (j=2; j<i; j++){
            if (i%j==0){
                break;
            }
        }
        if (i==j){
            sum +=i;
        }
    }
    System.out.print(sum);
  }
}

Try using the [Sieve of Eratosthenes](http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes) — Luiggi Mendoza, Aug 31 '13 at 23:54
@azzurroverde verifying if the number is a prime number gets too slow with this approach. Review the sieve of eratosthenes in the link in my comment to understand how you can improve this algorithm — Luiggi Mendoza, Aug 31 '13 at 23:58
I would use a long for the sum. The primes up to 2 million are likely to sum above 2^31 - 1. — G. Bach, Sep 01 '13 at 00:00
@Luiggi Mendoza, yes, this method is crazy. Both for the two for loops one inside the other, and for the use of the %. I also would advise the classical Eratosthenes method. But besides that, I was curious why he said that it didn't work. What happened? I was wondering if besides time there was some other problem. — azzurroverde, Sep 01 '13 at 00:02
@azzurroverde probably OP thinks that waiting too long for the program to finish means the program doesn't work as expected — Luiggi Mendoza, Sep 01 '13 at 00:03
YARC! (yet another **ridiculous** closure): a question about Java trial division algo with `int` overflow problem fixable by using `long` (in Java!) instead, is proclaimed to be a duplicate of, and already having an answer at the question about *the sieve of Eratosthenes in C++*, where the accepted answer suggests using *`long long`* type (in C++ that is!). Is there such a type at all in Java, `long long`??? **This is not even funny.** — Will Ness, Sep 02 '13 at 10:24
We've had this overflow on Project Euler 10 umpteen times. Since you can't abstract from the detail of the programming language used, here is one in Java: http://stackoverflow.com/questions/3045482/project-euler-problem-10-java-solution-not-working — starblue, Sep 04 '13 at 12:05
Java - check, trial division - check, overflow - check. Now let's close it with the legit duplicate. — Will Ness, Sep 04 '13 at 19:24

Stephen C · Accepted Answer · 2015-12-15T06:41:42.590

Your code could be improved by making the inner loop stop earlier. If a number N is not prime, then it must have at least one factor (apart from 1) that is less or equal to sqrt(N). In this case, this simple change should make the program roughly 1000 times faster.
For a simple and (more) efficient algorithm, read up on the Sieve of Eratosthenes.
Bug - your sum needs to be a long. An int will probably overflow.

Note that the classic formulation of Sieve of Eratosthenes needs a large array of booleans (or a bitmap) whose size depends on the largest prime candidate you are interested in. In this case that means a 2Mbyte array (or smaller if you use a bitmap) ... which is too small to worry about. Also, you can reduce the memory usage by sieving in stages, though it makes the code more complicated.

Dev Blanked · Answer 2 · 2013-09-01T05:41:04.133

Rather than trying to divide by all the numbers below i you could potentially keep the found prime numbers in a list and try to divide by those prime numbers (since any non prime number will be divisible by a prime number less than that).

public static long sumPrime2() {
    List<Long> primes = new ArrayList<>();
    primes.add(2L);
    primes.add(3L);
    long primeSum = 5;

    for (long primeCandidate = 5; primeCandidate < 2000000; primeCandidate = primeCandidate + 2) {
        boolean isCandidatePrime = true;
        double sqrt = Math.sqrt(primeCandidate);
        for (int i = 0; i < primes.size(); i++) {
            Long prime = primes.get(i);
            if (primeCandidate % prime == 0) {
                isCandidatePrime = false;
                break;
            }
            if (prime > sqrt) {
                break;
            }
        }
        if (isCandidatePrime) {
            primes.add(primeCandidate);
            primeSum += primeCandidate;
        }
        System.out.println(primeCandidate);
    }
    System.out.println(primes.size());
    return primeSum;
}

This gave the answer in 8 seconds

you can even stop adding primes after the sqrt of the top limit is reached, for a marginal speedup. You also don't need to check for `i < primes.size() ;` after a few initial iterations. you also don't need `isCandidateAPrime` flag, you can react to it right at the `if(prime > sqrt)` point. great stuff, anyway. :) — Will Ness, Sep 02 '13 at 12:09

Jonathan Marshall · Answer 3 · 2013-09-01T01:40:41.603

I suspect integer overflow in i, j, sum - try making them all longs. In the sample code you shouldn't be getting overflows as Java ints are meant to be 32 bit but at some stage you certainly will.

As already mentioned - i only needs to iterate to the square root of n. So I would replace this line:

for (i=2; i <n; i++){

With:

long limit=sqrt(n);
for (i=2; i <limit; i++){

Note that calculating the square root outside the program loops will also speed things up a bit.

Also the sieve algorithm would be faster but requires Java to create an array containing n elements and at some stage that is going to fail with insufficient memory.

`i` needs to iterate to `n`; it's `j` that needs to iterate to the sqrt of `i`. -- `< limit` is not right. :) — Will Ness, Sep 01 '13 at 15:53

score 0 · Answer 4 · answered Sep 01 '13 at 12:24

The best algorithm for this program uses the Sieve of 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

Then sumPrimes(2000000) returns the sum of the primes less than two million, in about a second. I'll leave it to you to translate to Java, with an appropriate data type for the sum. If you're interested in programming with prime numbers, I modestly recommend this essay at my blog.

I'm trying to find the sum of primes below 2 million in Java

4 Answers4

Linked