There is a huge number of ways to make this run faster.
First you save an awful lot of space by storing only odd numbers in the sieve. The only even prime is the number 2. Note that on a modern computer the time your algorithm takes is roughly equivalent to the amount of data that it reads and writes, so halving the space needed will half the execution time. So the bool at index \$i\$ represent the number \$2_i+1\$.
Now you only need to remove odd numbers. When you set everything to true initially, set array[0]
to false since 1 is not prime. Now when you remove multiples of a prime p, you know that all multiples less than \$p^2\$ have already been removed, so you start the loop for removing primes at \$p^2\$. And you increase by 2p at a time, because p*p
, (p+2)*p
, (p+4)*p
etc. are the odd multiples of p. And since the first prime you remove is \$p^2\$, you can stop the loop looking for primes when \$p^2\$ <= MAX.
Now things are a bit tricky: You look for the next prime p. For that you check a [i]
until you find one that is true. The index i maps to the prime p = 2i + 1
. \$p^2\$ is an odd number and the number \$p^2\$ is stored at the index j = (p^2 - 1) / 2
. So you clear the numbers a [j]
, a [j + p]
etc.
So far it's simple, now we get a bit more clever. Your MAX
is big, say \$10^9\$. When you remove the multiples of 3, you get a repeating pattern. For the numbers p = 1, 3, 5, 7, 9, 11, 13, 15, 17, you get the pattern (true, false, true), (true, false, true), (true, false, true) and so on. Three values repeating forever. Fill the first 15 numbers with that pattern, then remove the multiples of five: From (T,F,T, T,F,T, T,F,T, T,F,T, T,F,T) after removing the multiples of five you keep (T,F,F, T,F,T, T,F,T, T,F,T, F,F,T). This pattern of fifteen bools will repeat forever. You make 7 copies giving 105 numbers and remove the multiples of 7. You make 11 copies giving 1155 numbers and remove the multiples of 11. You make 13 copies giving 15,015 numbers and remove the multiples of 13. You may make 17 copies giving 255,255 numbers and remove the multiplies of 17. This is very quick because you didn't have a billion numbers, only a few hundred thousand. When you're done you duplicate the data into the whole array with memcpy
. For the last part you need to watch out not to overwrite the end of the array. That was only six numbers, but these 6 numbers do a very significant part of the work!
For the other primes, you would remove all their odd multiples. We can do that faster. Take p = 101. You would remove 101p, 103p, 105p, 107p and so on. But 105p is divisible by 3, so it has been removed already. Same for 111p and so on. So here is what you do: You remove \$p^2\$. If p+2
is not divisible by 3, you also remove (p+2)*p
. The next number you would try to remove would be a multiple of 3. So instead of increasing the number you remove by 2p each time, you increase by 4p (avoiding the multiple of 3), then by 2p, then again by 4p, 2p, 4p, 2p and so on. That saves one third of the work.
One more improvements: Instead of using one byte to store each number, you use only one bit. This means you need to perform shifting operations to access each bit, but the amount of memory used shrinks by a factor 1. That lets you handle much bigger numbers, and less memory will work quicker.
And the final, big one: Optimise memory accesses. Let's say you have MAX = 1 billion, and use one bit per odd number = 62.5 megabyte. That's more than fits into your processor cache. Let's say you have 2MB L3 cache = 32 million numbers. In that case you perform the sieve operation completely for the first 32 million numbers. This will run a lot faster because your data is all within the L3 cache. Let's say you have 256KB L2 cache = 4 million numbers. In that case you perform the sieve operation completely for the first 4 million numbers, then the next four million, and so on. This is even faster because now all the data you use is within the L2 cache and can be read / written very quickly.
\$
does the trick \$\endgroup\$calloc
to get already-zeroed memory, and have your sieve set it to true. Then you can avoid a costlymemset
. \$\endgroup\$