# Thread: Efficient way to find Primes and sums of primes

1. Señor Member
Join Date
Jan 2014
Posts
184
Rep Power
0

## Efficient way to find Primes and sums of primes

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

2. Senior Member
Join Date
Jan 2013
Location
Northern Virginia, United States
Posts
5,738
Rep Power
10

## 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

3. ## Re: Efficient way to find Primes and sums of primes

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

4. Señor Member
Join Date
Jan 2014
Posts
184
Rep Power
0

## 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?

5. ## 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

#### Posting Permissions

• You may not post new threads
• You may not post replies
• You may not post attachments
• You may not edit your posts
•