Improving performance

exercise No. 158

Improving prime number calculation performance

Q:

Our current algorithm checking for prime numbers wastes a lot computing power. Consider testing candidate value 143. Currently our implementation works like: 

143 %  2 == 0 ? No.
143 %  3 == 0 ? No.
143 %  4 == 0 ? No.
143 %  5 == 0 ? No.
143 %  6 == 0 ? No.
143 %  7 == 0 ? No.
143 %  8 == 0 ? No.
143 %  9 == 0 ? No.
143 % 10 == 0 ? No.
143 % 11 == 0 ? Yes ==> 143 is not prime

Learning from prime factorization it actually suffices testing only prime values rather than all integer values up to the already discussed square root limit: 

143 % 2 == 0 ? No.
143 % 3 == 0 ? No.
143 % 5 == 0 ? No.
143 % 7 == 0 ? No.
143 % 11 == 0 ? Yes ==> 143 is not prime

Thus only considering primes we may save a lot of operations. The trade off is even bigger for higher prime number values. This algorithm requires storing all computed prime numbers without gaps thereby reducing required computation time.

Implement the above algorithm and compare the elapsed execution time.

Tip

Storing prime numbers requires an array (or another type of container). Since we do not know the number of prime numbers beforehand the required array size is not yet known when starting the application. There are different possibilities to deal with this problem:

  • You may want to reuse your unsorted IntegerStore implementation to provide a dynamically growing array of integer values.

  • You may again implement a kind of amortized doubling algorithm allowing for dynamic growth.

A:

We save ~80% of execution time:

Found 664579 prime numbers within 2.641 seconds.

So the current implementation indeed adds a substantial benefit with respect to performance.

Prev  Up  Next
A simple algorithm  Home  The median of a given sample.