Improving performance
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. TipStoring 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:
|
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. |