Primes, part 2(ish)
Previously, I was timing a function to list primes between 1 and an end number. The function worked and all, but it was a bit slow: while it could calculate all the primes between one and 100 in 130 microseconds, it got worse and worse as the numbers g rew bigger. Going from one to one million took 11.6 seconds, while going from one to ten million took a whopping five minutes and 19 seconds. At least, that’s what Jupyter claims. It felt like it was taking much longer. And going from one to 100,000,000 — well, I had work in the morning.
So let’s see if we can make this function better (“Can we fix it?” “Yes we can!”). Here’s what it currently looks like:
In plain English (or ‘explaining technical stuff to my mom’ mode), what this is doing is going through all the numbers between one and the end number and checking to see if it’s a prime by trying to divide it by all the numbers. If you can’t divide it, it’s prime and you stick it in the list of primes (and if Mom doesn’t understand it now, I’d have to just tell her that it’s magic). I actually cheated here and put in the upper limit of x**0.5 + 1 (the square root of x), so the function isn’t entirely optimized, but still.
So there are two ways that I could make this function quicker: speed up the iteration, or speed up the prime-checking process. And the best way to do that is by having it iterate over fewer numbers or having it check fewer numbers.
With that in mind, here’s my new version of the prime-checker:
Let’s start by looking at the iteration. A prime number will always be of the form 6x+1 or 6x-1 (Reasoning: all numbers are going to be of the form 6x + y, where y is between 0 and 5. Sounds good so far, right? If y = 0, 2, 4 then the number is going to be even and therefore not prime (unless the number is 2, which is a special case). 6x + 3 is going to be divisible by 3, so that’s out. So the only options that aren’t automatically ruled out for prime numbers are 6x+1 and 6x+5. QED)
The second thing I did was reduce the numbers to be checked. Every composite number is going to be the product of two or more prime numbers, so instead of checking every single number to see if it divides, you can just check the primes. Easy peasy.
Question: does this run any faster?
Nope. Not even a little bit. Booger.
So what gives? The answer lies in the very last line: print (otherPrimeList(51)). Hint: it’s because my function is buggy. To be continued…