# Sieve of Eratosthenes

Gauri Shankar Iyer

Greenhorn

Posts: 6

posted 5 years ago

My first attempt at writing the algo for finding primes in a range using the Sieve of Eratosthenes.

(Wikipedia: http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes).

I'm wondering what are the bad practices you can see in this small piece of code, and any optimizations you see fit? Also, looking to

Some observations you might find interesting:

- For the range (1, 500000), it takes about 5 seconds with the code below, on my AMD dual core machine.

- On line 33, changing the Math.pow(variable, 2) to (variable * variable) reduces the running time to 2 seconds!

- The reduction of lines 59, 60, 61 into line 62 has no effect whatsoever. Removing explicit allocations doesn't necessarily mean implicit VM allocations will be removed too.

(Wikipedia: http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes).

I'm wondering what are the bad practices you can see in this small piece of code, and any optimizations you see fit? Also, looking to

**reduce**the number of lines of code in any way possible. Some criticism will be very helpful. Thanks.Some observations you might find interesting:

- For the range (1, 500000), it takes about 5 seconds with the code below, on my AMD dual core machine.

- On line 33, changing the Math.pow(variable, 2) to (variable * variable) reduces the running time to 2 seconds!

- The reduction of lines 59, 60, 61 into line 62 has no effect whatsoever. Removing explicit allocations doesn't necessarily mean implicit VM allocations will be removed too.

posted 5 years ago

any sort of built-in operators (*,/,+,-) are always going to be less expensive to use than recursive functions like Math.pow, because functions have to be called, execute their own code and possibly call other functions, then they have to return. And for a smaller program you can never tell the difference. But when you are trying to do 500,000 calculations, that overhead adds up quickly.

Hunter

Hunter

"If the facts don't fit the theory, get new facts" --Albert Einstein

Campbell Ritchie

Sheriff

Posts: 48924

58

Lester Burnham

Rancher

Posts: 1337

Campbell Ritchie

Sheriff

Posts: 48924

58

Gauri Shankar Iyer

Greenhorn

Posts: 6

Campbell Ritchie

Sheriff

Posts: 48924

58

posted 5 years ago

I wrote mine with a boolean[] array. Set all the values to

`true`(except 0 and 1, which are implicitly`false`) and change all the places found with the sieve to`false`. Start looping at 2. It is easier to have an array 1 size larger than your range, so you can use the index to represent the number.
Paul Beckett

Ranch Hand

Posts: 96

posted 5 years ago

see problem 10 "Calculate the sum of all the primes below two million" on projecteuler.net. If you can solve the problem then a solution pdf is provided giving hints (including pseudo code) for how to efficiently do a sieve (solves in much less than a second on a modest PC). Your code should be more than sufficient to solve the problem and is way more efficient than my first attempt where I didn't even use a sieve. The solution pdf will explain things much more eloquently than I could here.

Note: Campbell is correct to use a boolean[] but this can be optimized even further thus reducing the size of the array.

(i) no even number other than 2 can be a prime

(ii) can you reduce the max number you need to check for?

Note: Campbell is correct to use a boolean[] but this can be optimized even further thus reducing the size of the array.

(i) no even number other than 2 can be a prime

(ii) can you reduce the max number you need to check for?

Campbell Ritchie

Sheriff

Posts: 48924

58

posted 5 years ago

I tried it with a boolean[] array yesterday, taking about 3 seconds to sieve from 2 to 100000000 (1e8), but it took about 1 minute to display all those numbers on screen. For 2 to 1000000000 (1e9) I suffered an OutOfMemoryError.

Campbell Ritchie

Sheriff

Posts: 48924

58

Paul Beckett

Ranch Hand

Posts: 96

posted 5 years ago

ok, I'd missed that bit

Using the square root would be more efficient in this case. So work out the square root of the end number (crosslimit) before the loop and then the termination expression becomes "end<crosslimit".

Using a boolean array you can change your increment expression to increment the loop by the number you are currently removing multiples of (runningPrime in the original code).

My algorithm takes <1.5 seconds to work out all the primes 1e8 but also gets an OutOfMemoryError with 1e9. Obviously the time taken is relative to the performance of the machine.

My version of the sieve:

I think the squaring allows for that. But surely it is simpler to use the square root?

ok, I'd missed that bit

Using the square root would be more efficient in this case. So work out the square root of the end number (crosslimit) before the loop and then the termination expression becomes "end<crosslimit".

Using a boolean array you can change your increment expression to increment the loop by the number you are currently removing multiples of (runningPrime in the original code).

My algorithm takes <1.5 seconds to work out all the primes 1e8 but also gets an OutOfMemoryError with 1e9. Obviously the time taken is relative to the performance of the machine.

My version of the sieve:

Campbell Ritchie

Sheriff

Posts: 48924

58

posted 5 years ago

Are you using false == prime? If so, what about 0, which is an exact multiple of every number, but is not a "natural" number? And what about 1, which doesn't divide by any other numbers, but is not usually considered prime?

I seemed to get a different result from yours when I printed the numbers out.

I think it runs in quadratic time.Paul Beckett wrote: . . . the time taken is relative to the performance of the machine. . . .

Are you using false == prime? If so, what about 0, which is an exact multiple of every number, but is not a "natural" number? And what about 1, which doesn't divide by any other numbers, but is not usually considered prime?

I seemed to get a different result from yours when I printed the numbers out.

~/java$ java Eratosthenes

Time for sieving 0.001s Please push "enter" to continue.

Primes found:

2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97

Total of all those primes = 1060

Duration by Paul's method = 0.002s

Please push "enter" to continue.

Primes found by Paul's method:

4 7 10 12 13 16 17 19 22 24 25 27 28 31 32 34 37 38 40 42 43 45 46 47

Total of all those primes = 659

Kurt Van Etten

Ranch Hand

Posts: 98

posted 5 years ago

Well, that raises some interesting questions... How much memory does the Java VM use to store a boolean value? I'm guessing one byte on most platforms. (Does Java have anything similar to the C sizeof operator? It would be nice to be able to estimate available resources before attempting a memory allocation.) In that case, you could increase the range of your sieve by using bitwise operators to store 8 0/1 values per byte, with a bit of a performance trade-off.

Of course that would only increase your range by a factor of 8. To get a truly big sieve, you'd need to write the values out to disk. With some judicious buffering and separate threads to handle the I/O, the performance should still be reasonable.

Campbell Ritchie wrote:I tried it with a boolean[] array yesterday, taking about 3 seconds to sieve from 2 to 100000000 (1e8), but it took about 1 minute to display all those numbers on screen. For 2 to 1000000000 (1e9) I suffered an OutOfMemoryError.

Well, that raises some interesting questions... How much memory does the Java VM use to store a boolean value? I'm guessing one byte on most platforms. (Does Java have anything similar to the C sizeof operator? It would be nice to be able to estimate available resources before attempting a memory allocation.) In that case, you could increase the range of your sieve by using bitwise operators to store 8 0/1 values per byte, with a bit of a performance trade-off.

Of course that would only increase your range by a factor of 8. To get a truly big sieve, you'd need to write the values out to disk. With some judicious buffering and separate threads to handle the I/O, the performance should still be reasonable.

Paul Beckett

Ranch Hand

Posts: 96

posted 5 years ago

I didn't include it before but my summing is done like so:

So a prime is false, don't think it matters which way round you do it. With prime = false then I don't need to explicitly set every value in the array to true before sieving.

The array doesn't contain even numbers so have to handle 2 as a special case. Other than that the value in the array at index i represents the number 2i+1, so index 3 represents the number 7.

Where maxNumber=12:

sieve: [false, false, false, false, true]

index: [ 0, 1, 2, 3, 4]

numbers: [ 1, 3, 5, 7, 9]

Obviously 1 is not a prime number so notice that when iterating the sieve always start at index 1.

Also my sieveBound should have been limit/2 instead of "(limit-1)/2".

Campbell Ritchie wrote:Are you using false == prime? If so, what about 0, which is an exact multiple of every number, but is not a "natural" number? And what about 1, which doesn't divide by any other numbers, but is not usually considered prime?

I seemed to get a different result from yours when I printed the numbers out.

I didn't include it before but my summing is done like so:

So a prime is false, don't think it matters which way round you do it. With prime = false then I don't need to explicitly set every value in the array to true before sieving.

The array doesn't contain even numbers so have to handle 2 as a special case. Other than that the value in the array at index i represents the number 2i+1, so index 3 represents the number 7.

Where maxNumber=12:

sieve: [false, false, false, false, true]

index: [ 0, 1, 2, 3, 4]

numbers: [ 1, 3, 5, 7, 9]

Obviously 1 is not a prime number so notice that when iterating the sieve always start at index 1.

Also my sieveBound should have been limit/2 instead of "(limit-1)/2".

Campbell Ritchie

Sheriff

Posts: 48924

58

Paul Beckett

Ranch Hand

Posts: 96

posted 5 years ago

you didn't copy anything incorrectly. The implementation you have used of my version of the sieve is correct I think. It is the printPrimes method that is incorrect. You are printing out the index of any "true" in the array. Whereas in my implementation of the sieve, "false" is a prime. And then instead of the index of the "false" elements you need to use 2i+1 to find the real number and start iterating at index 1.

Obviously you have identified a big flaw in the method I've used - its difficult to understand what is going on!!! However this is a java implementation of the method from Project Euler problem 10 solution pdf (section 10.2.2). I prefer to make code readable as a first priority and then only reduce readability to optimise if absolutely necessary but for project euler execution speed seems to be the priority over all others.

Obviously you have identified a big flaw in the method I've used - its difficult to understand what is going on!!! However this is a java implementation of the method from Project Euler problem 10 solution pdf (section 10.2.2). I prefer to make code readable as a first priority and then only reduce readability to optimise if absolutely necessary but for project euler execution speed seems to be the priority over all others.

Campbell Ritchie

Sheriff

Posts: 48924

58

posted 5 years ago

Please post working code, which we can actually execute and understand the output of. You ought to have posted the printing method as well, so we can see a set of prime numbers. If I had seen an output of all non-prime numbers, I would quickly have worked out that I was printing the wrong half of the array.

I don't think Project Euler

I don't think Project Euler

**do**want speed above all else. I think they want us to think up a correct solution.
Paul Beckett

Ranch Hand

Posts: 96

posted 5 years ago

The sieve I posted in my second post is a fully functioning sieve minus the method declarations.

My version of the sieve was for solving the project euler problem 10 and doesn't need a printing method for that purpose. In my third post I did provide the complete summing functionality which shows how to convert an array element to a prime number. Also I provided a "diagram" of the sieve, the array indexes, and the corresponding number the array index represented.

Campbell Ritchie wrote:Please post working code, which we can actually execute and understand the output of. You ought to have posted the printing method as well, so we can see a set of prime numbers

The sieve I posted in my second post is a fully functioning sieve minus the method declarations.

My version of the sieve was for solving the project euler problem 10 and doesn't need a printing method for that purpose. In my third post I did provide the complete summing functionality which shows how to convert an array element to a prime number. Also I provided a "diagram" of the sieve, the array indexes, and the corresponding number the array index represented.

posted 5 years ago

I'll just add my 2cents. Using a BitSet should help with memory issues and appears to be plenty fast. On my machine (your milage may vary) I ran 500,000 numbers in 0.02 seconds.

Understanding the scope of the problem is the first step on the path to true panic

Mike Simmons

Ranch Hand

Posts: 3076

14

posted 5 years ago

Yeah - boolean[] arrays seem to often be implemented using 8 bits for each boolean. The boolean array is faster, but not by enough to justify using eight times as much memory (IMO).

On my machine, it ran in 0.02 sec as well. And the same code can run 500,000,000 numbers in 18-19 sec. (Going to 1,000,000,000 would require changing the standard JVM memory settings, so I stopped there.) I got it down to 11-12 sec by replacing the second for loop with this:

As long as you've already handled all the multiples of 2, we might as well only deal with the

A next step might be to eliminate all multiples of 2 or 3. My guess is that might reduce the time by about 1/6 (since the only new skips are for multiples of 3 which aren't already multiples of 2, like 9, 15, 21, 27, 33... etc). Making the code somewhat more complex to boot. Not sure it's worth it. But I thought I'd toss it out there; maybe someone can use the idea to good effect.

Carey Brown wrote:I'll just add my 2cents. Using a BitSet should help with memory issues and appears to be plenty fast.

Yeah - boolean[] arrays seem to often be implemented using 8 bits for each boolean. The boolean array is faster, but not by enough to justify using eight times as much memory (IMO).

Carey Brown wrote: On my machine (your milage may vary) I ran 500,000 numbers in 0.02 seconds

On my machine, it ran in 0.02 sec as well. And the same code can run 500,000,000 numbers in 18-19 sec. (Going to 1,000,000,000 would require changing the standard JVM memory settings, so I stopped there.) I got it down to 11-12 sec by replacing the second for loop with this:

As long as you've already handled all the multiples of 2, we might as well only deal with the

*odd*multiples of i at this point.

A next step might be to eliminate all multiples of 2 or 3. My guess is that might reduce the time by about 1/6 (since the only new skips are for multiples of 3 which aren't already multiples of 2, like 9, 15, 21, 27, 33... etc). Making the code somewhat more complex to boot. Not sure it's worth it. But I thought I'd toss it out there; maybe someone can use the idea to good effect.

Kurt Van Etten

Ranch Hand

Posts: 98

posted 5 years ago

I was curious about how big of a time hit this would make, so I switched my previous version to use a BitSet instead of an array (keeping everything else the same), and it took about 2.5 times longer to run. So I suppose you have to weigh whether the time or memory is more important to you. Now I wonder how much of the time hit is due to the overhead for the function calls. I ought to try implementing the bit operations directly in an array and see how much of an improvement that makes.

Carey Brown wrote:I'll just add my 2cents. Using a BitSet should help with memory issues and appears to be plenty fast. On my machine (your milage may vary) I ran 500,000 numbers in 0.02 seconds.

I was curious about how big of a time hit this would make, so I switched my previous version to use a BitSet instead of an array (keeping everything else the same), and it took about 2.5 times longer to run. So I suppose you have to weigh whether the time or memory is more important to you. Now I wonder how much of the time hit is due to the overhead for the function calls. I ought to try implementing the bit operations directly in an array and see how much of an improvement that makes.

Kurt Van Etten

Ranch Hand

Posts: 98

posted 5 years ago

I tried this out. Instead of adding 2 times the current prime each time you mark an element in the sieve, you alternate adding 4 times and 2 times the current prime. Unfortunately the time was essentially unchanged--even though I needed to mark 1/3 fewer elements in the sieve for each prime greater than 3, the time savings was apparently offset by the slight increase in complexity.

Mike Simmons wrote:A next step might be to eliminate all multiples of 2 or 3. My guess is that might reduce the time by about 1/6 (since the only new skips are for multiples of 3 which aren't already multiples of 2, like 9, 15, 21, 27, 33... etc). Making the code somewhat more complex to boot. Not sure it's worth it. But I thought I'd toss it out there; maybe someone can use the idea to good effect.

I tried this out. Instead of adding 2 times the current prime each time you mark an element in the sieve, you alternate adding 4 times and 2 times the current prime. Unfortunately the time was essentially unchanged--even though I needed to mark 1/3 fewer elements in the sieve for each prime greater than 3, the time savings was apparently offset by the slight increase in complexity.

Mike Simmons

Ranch Hand

Posts: 3076

14

posted 5 years ago

Yeah, I was getting very similar results, with the same skip-2/skip-4 idea. Seems like the added calculations to figure out which elements to hit offset the savings of hitting fewer elements. Annoying. I was looking for cleaner ways to refactor it, but not seeing much improvement. Oh well.

Paul Beckett

Ranch Hand

Posts: 96

posted 5 years ago

The BitSet is more efficient in terms of memory usage - no argument there. However both BitSet and boolean[] will hit the limit soon enough of being indexed by an int.

Arbitrarily allocating Xmx768m, my boolean[] can handle 1e9 in 15s with the BitSet in 36s. The point being 1e9 is approximately half of Integer.MAX_VALUE. So why did I stop at 1e9 and not go on to Integer.MAX_VALUE? My implementation doesn't contain even numbers in the sieve so requires an i*2 calculation to work out the real number from the index (see earlier posts) so 1e9 is approximately the max value I can handle without recoding. So with recoding then memory requirement would be fulfilled by Xms1536m. I'm not advocating always chucking more memory at a problem but in this instance IMHO the inherent Integer.MAX_VALUE limit is more of a concern than the memory efficiency.

Arbitrarily allocating Xmx768m, my boolean[] can handle 1e9 in 15s with the BitSet in 36s. The point being 1e9 is approximately half of Integer.MAX_VALUE. So why did I stop at 1e9 and not go on to Integer.MAX_VALUE? My implementation doesn't contain even numbers in the sieve so requires an i*2 calculation to work out the real number from the index (see earlier posts) so 1e9 is approximately the max value I can handle without recoding. So with recoding then memory requirement would be fulfilled by Xms1536m. I'm not advocating always chucking more memory at a problem but in this instance IMHO the inherent Integer.MAX_VALUE limit is more of a concern than the memory efficiency.

Consider Paul's rocket mass heater. |