Category: Project

This was one of my first major projects when I started programming. I remember starting this project after seeing a small snippet of logic required to search for prime numbers on a Stack Overflow page, and being very surprised by its simplicity.

I began with the most simple search, with the user inputting a single number and getting the code to try every number beneath it using modulo to check if that number fits into it with 0 remainder.

I then expanded my code to have a specific cap; the code would now check every number from 0 to that number to see if they were prime.

Threading

To improve the speed of my prime number generator, I implemented a threading system. This used Python’s threading module to split the process of checking every number under the target number into different jobs. I made a script using 4 and 8 threads. So, for example, the 4 threaded version would take the number 80, and give thread 1 the numbers 3 to 20, thread two 21 to 40, thread three 41 to 60, and thread four 61 to 79.

This slowed the code down initially, due to the computational overhead of starting up the threads I presume, but as soon as the cap reached a critical point where the number was large enough, the threaded version of the code overtook the single threaded version.

More improvements

I went back to this project months later and had another crack at it: here I made a few massive speed improvements.

First of all I set the code to completely skip the even numbers when iterating to the cap. Meaning it never even begins to check if 4, 6, 8… are prime.

Second of all I implemented a similar thing into the iteration for the checker number, meaning the code does not check if 2 or 4 or 10 go into the target number, as all the evens are being skipped now so those numbers are not necessary to check.

Then I made a series of realisations concerning the range of numbers under the current target which are necessary to be checked:

First, I realised that only the numbers under half of the target need to be checked, as numbers above half will just be a repeat of factor pairs with a one of those numbers being below half, essentially the same thing but reversed.

I then found online that this rule goes even further, and only the numbers up to the square of the target number need to be checked. This is because, apart from the square root factor itself, in every other factor pair their must be one number lower than the square root of the number. This is because if you increase one of the numbers in the pair, the other must decrease in order to still reach the same number. This means that if there is a factor for that number, one of those numbers in that pair will be lower than the square root, and checking that number will break the loop, meaning the other number never even has to be reached in order to prove no prime.

A final major breakthrough was made by my friend when he realised the only numbers you have to use to check if a number has factors are primes. This is because in a prime is made up of no factors (other than itself and 1), so you can be sure when using a prime that no number underneath it are factors of it, meaning that the number has essentially already been checked. For instance, the current system checked 3; it divided the target by 3 to see if it fits in perfectly. But by doing this you also inadvertently disprove that any multiple of 3 will ever fit into that number. So 6, 9, 12, 15, 18… can also never be factors, because if they were factors, 3 would also be a factor. So using only primes to check for factors skips out many numbers that have technically already been disproven by a past multiple.

To check if not prime: if any prime under the square root of the number % the number = 0

After implementing theses features – and without any threading – the checker completely blew away the old system, even at the much higher numbers!

Next I need to program this new logic but with threading too!