Efficient way to find Primes and sums of primes

Code:

`class Program {`

public static void main (String[] args) {

long max = 200; //add up all primes up to 200

long ans = 0;

for(long x = 2; x < max; x++) {

if(isPrime(x)) {

ans += x;

}

}

System.out.println("Answer is: " + ans);

}

public static boolean isPrime(long x) {

for(long z = 2; z < x; z++) {

if(x % z == 0){

return false;

}

}

return true;

}

}

This code adds up all of the primes before a certain number (max). Unfortunately, it is much too slow when you get up to bigger numbers - how can I do this more efficiently.

BEFORE YOU ANSWER: Don't point me to the sieve of Eratosthenes, if that's what you are about to post - I'm not quite sure how to implement that kind of method into my program, so if you know, please explain and give me an example. Thanks

Re: Efficient way to find Primes and sums of primes

You don't need to the sieve to find the primes. But what you can do is store each prime you find and then only divide by those up to the square root of the target. It is still a trial by division method so it is sub-optimal to an actual sieve. More information is here --> Trial division - Wikipedia, the free encyclopedia. And don't forget to check out the reference articles.

Regards,

Jim

Re: Efficient way to find Primes and sums of primes

Quote:

Originally Posted by

**AlexGraal** BEFORE YOU ANSWER: Don't point me to the sieve of Eratosthenes, if that's what you are about to post - I'm not quite sure how to implement that kind of method into my program, so if you know, please explain and give me an example. Thanks

Oh cool, you want advice but you don't want good advice because you already seem to know that you can't implement it ...

kind regards,

Jos

Re: Efficient way to find Primes and sums of primes

Hmmmm, if only looking at the first half of the sentance, I guess that's what you'd get out of it. But the second half states what I was trying to say - aka, don't just tell me that it exists, because I already know about it. I'd much rather see how to implement it as I tried to and couldn't.

Well, I guess since you answered and know about it, you can confirm or deny the way I was thinking about it.

I was going to make an arraylist with all of the possible integers from 2 to 2000000, then I would start with the first integer, loopthrough the arraylist and remove anything that is evenly divisible by 2. Then move on to 3 and continue. Is that correct?

And thanks Jim for the helpful reply :)

Re: Efficient way to find Primes and sums of primes

Have a look at the BitSet class; it is way more efficient than an ArrayList for this purpose.

kind regards,

Jos