How to improve my prime-number-sum algorithm?

Question

I have written a code which returns the sum of all the prime numbers whose values are below 2 million. But it is taking huge time for the result(waited for 30 minutes for the answer).

Can anyone suggest how to make the algorithm more efficient?

public static void main(String[] args){

    int i,primeNum=1,sumPrime=0,c=0;
    while (primeNum<2000000){
            int factors=0;
            for(i=1;i<=primeNum;i++){
                if((primeNum%i)==0) {
                    factors++;  // total number of factors                  
                }
            }               
            if(factors==2){ 
                if(primeNum<2000000){
                    sumPrime=primeNum+c;
                    c=sumPrime;
                }
                System.out.println(primeNum);   
            }

            primeNum++;

        }
        System.out.println(sumPrime);
    }

Answer 1

In Python, you can accomplish it this way. Compared to some previous solutions, I try not to change the isPrime vector once I cross $\sqrt{n}$

import math
def sum_primes(nmax):
    maxDivisor=int(math.floor(math.sqrt(nmax)))
    isPrime=[False,False]+range(2,nmax+1)

    for i in range(2,maxDivisor+1):
       if isPrime[i] is not False:
           for dummy in range(i*2,nmax+1,i):
               isPrime[dummy]=False

    print (sum(isPrime))

Answer 2

It's the loop in the loop that causes the code to be slow. Here is some code i found that runs with same criteria in only a few seconds:

void setup() {
  for (int i = 1; i<2000000; i++) {
    if (isPrime(i)) {
      System.out.println(i);
    }
  }
}

boolean isPrime(int number) {
  if (number < 2) return false;
  if (number == 2) return true;
  if (number % 2 == 0) return false;
  for (int i = 3; (i*i)<=number; i+=2) {
    if (number % i == 0 ) return false;
  }
  return true;
}

Answer 3

This function sums the primes less than n using the Sieve of Eratosthenes:

function sumPrimes(n)
    sum := 0
    sieve := makeArray(2..n, True)
    for p from 2 to n step 1
        if sieve[p]
            sum := sum + p
            for i from p * p to n step p
                sieve[i] := False
    return sum

I'll leave it to you to translate to Java. For n = 2000000, this should run in one or two seconds.

Answer 4

This part is very innefficent:-

for(i=1;i<=primeNum;i++){
  if((primeNum%i)==0) {
    factors++;  // total number of factors                  
  }
}     

The counts the total number of factors. Since all you are interested in is if the number is prime or not, the number of factors is not required. The test should be if there is a factor that isn't 1 or the number being tested. So you can do this:-

boolean is_prime = true;
// start at 3 as 1 is always a factor and even numbers above 2 are definately not prime, terminate at n-1 as n is also a factor
for(i=3;i<primeNum;i+=2){
  if((primeNum%i)==0) {
    is_prime = false;
    break;
  }
}

This is now more efficient for non-primes. For primes it is doing too much, factors come in pairs: if a.b == c then a <= sqrt(c) and b >= sqrt(c), so the loop can safely terminate at sqrt(primeNum). You could compute sqrt(primeNum) before the loop but that would usually require using floating point functions. Instead or terminating when i > sqrt(primeNum), terminate the loop when i.i > primeNum. You can also remove the i.i multiplication and replace it with an extra variable and a couple of adds (left as an exercise for the reader).

Another approach is to use a sieve, as others have mentioned, which is a simple method when there's a fixed upper limit to the search space. You can make a version that has no upper limit (memory size not withstanding) but is quite tricky to implement as it requires a bit of dynamic memory management. Not sure if a simple sieve would be faster than the factor search as you will be hitting memory with the sieve which has a big effect on speed.

Answer 5

Reduce the usage of if conditions. It slows down your code. Try to use ternary operators if possible if this affects your speed even though it is not recommended in java 1.5.

Try this solution:

if( (factors==2)&&(primeNum<2000000) )

instead of repeated if conditions and post any difference.

Answer 6

There are multiple things:

1. When you want to determine more than one prime sieve algorithm is far better. (Google for sieve of Eratosthenes, and then sum up).

2. Even when using the naive algorithm, like you do, there are several improvements possible:

   1. Think of it: except the first even prime, all others are odd, so you should not do a /primeNumber++ in your loop, but more a primeNumber+=2 (and actually start the loop not with 1). [ Runtime halfed ]

   2. You Check in your inner loop for all numbers smaller than the prime candidate if they are a factor of it. There you can also skip all even numbers (and increase always by two). [Runtime almost halfed ].

   3. In your inner loop you can save even more. You dont need to check for all number < prime, but only up to < sqrt(prime). Because when a number divides the prime, there must be always two factors and one of them must be smaller(or equal) to the square root. [ Runtime "rooted" ]

   4. You dont want the factors of the prime, you only want to know if the number is prime or not. So when you know it is not prime, do NOT continue testing it (i.e. break out of you loop when you got the first factor (to make that easier, you should NOT test for the 1 and the number itself) - This will save you a huge amount of time. [ Runtime even more reduced. ]

So with this tips even your naive approach without sieve will result in a runtime less than 2 minuted (sqrt(15/4)).

Answer 7

check sieve of Atkin algorithm. It is an optimized version of ancient sieve of Eratosthenes.

Answer 8

I won't provide you a full answer, as the objective of Project Euler (where I'm guessing you got that problem from), is to think about things and come up with solutions.

Anyway, I will leave some steps that will guide you in the right way:

• Break up your code into two methods:
  • Eratosthenes sieve (http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes) which is quite trivial, and will return you a list of all prime numbers under 2M.
  • A method that simply sums up all the values returned by the Sieve.

This will be very efficient, if you implement the sieve correctly, it should bring down your execution time to a couple of seconds.

Answer 9

Actually the code is not optimized enough because at worst case, time taken to execute the loop would be more. You can even optimize the code for finding prime number as well.Try the below code and it works fine

public static void main(String[] args) {
    //you know 2 is the only even prime.
    int sum = 2;
    for (int i = 3; i <= 2000000; i++) {
        boolean prime = isPrime(i);
        if(prime){
            sum+=i;
        }
    }
    System.out.println("Sum = " + sum);
}

/*
 * we know 2 is the “oddest” prime – it happens to be the only even prime
 * number. Because of this, we need only check 2 separately, then traverse
 * odd numbers up to the square root of n
 */
public static boolean isPrime(int n) {
    // check if n is a multiple of 2
    if (n % 2 == 0)
        return false;
    // if not, then just check the odds
    for (int i = 3; i * i <= n; i += 2) {
        if (n % i == 0)
            return false;
    }
    return true;
}

Answer 10

Your algorithm is really inefficient, for algorithms to calculate prime numbers look here. Summing them up once you have them shouldn't be the problem.

Answer 11

For a start:

• Does the for(i=1;i<=primeNum;i++){ loop have to run to primeNum or maybe just to the square root of primeNum?
• does i have to be incremented by 1 or is 2 more efficient?
• ...