I created a small C project for prime number generation, I use a couple of algorithms to see how the they scale.
The “basic” algorithm uses a simple for loop for every integer from 2 to n. To check whether a value is prime, it iterates over every single value from 2 to the value being checked, to see if its remainder is 0, if none of the values have a remainder of 0, then it is a prime number. Even though it’s a simple algorithm, it is really slow, as it can be seen from the graph.
I made a better version of this basic algorithm by changing the function for checking whether something is a prime. Instead of checking for every value from 2 to value, I instead check every value from 2 to square root of that value. This is because at least one factor of an non-prime number N must be lower than the square root of N. Using this we can speed up the algorithm a lot.
I also created another version of the the “better” algorithm by adding a cache mechanism as well, however the cached algorithm has lower performance, which is surprising.
I also tried another type of algorithms for generating primes, they are called sieves, I spesifically started with Eratosthenes’ sieve algorithm. It works by generating a list of values from 2 to n(n being the limit), it then defines p to be 2 and marks all multiples of it within the list. After marking every multiple, p becomes the next smallest value greater than p(for example, p becomes 3 if p was 2 before). It repeats until its done. Numbers that were not marked are primes.
There are different versions of the sieve algorithms created by mathematicians. There is Eratosthenes’s Sieve, Pritchard’s Sieve, Atkin’s Sieve and Sundaram’s Sieve. From my testing, it seems like both Atkin’s and Sundaram’s Sieves are the best.
Overall, this was a simple project but I definitely learned some stuff. I would like to test out more algorithms and do better testing next time.
