— EDIT —

There is a whopping whole in my algorithm below, it doesn’t account for all possible prime numbers. Here is a full proof prime number checker:

from math import *
def is_prime(n):
# all even values of `n` are not prime
# except for 2, which is
if not n % 2 and not n == 2:
return False
# test only the odd values from 3..sqrt(n) inclusive
else:
for i in range(3, floor(sqrt(n))+1):
if not n % i:
return False
return True

In my previous post, “Refactoring in 2 Dimensions” I used an algorithm to calculate prime numbers:

def is_prime(n):
for i in range(2, n):
if not n % i:
return False
return True

The asymptotic runtime of this is O(n^2) which means for large values of `n` this gets really slow! Tested with a range of values (2, …, 100 000) the algorithm VISIBLY slowed for values of n > 50 000.

In calculating primes, you really only need to test each value of n against the set (2, …, 9). Optimising the algorithm then:

def optimised_prime(n):
x = n if n < 10 else 10
for i in range(2, x):
if not n % i:
return False
return True

This results in constant runtime! Win 🙂

–> There is a hole in this: 103 is divisible by 13, but this returns 103 as prime. So I need to tweak the optimised algorithm (maybe testing against (2, …, n/2) or (2, … n^(1.2))???? Work to be done

### Like this:

Like Loading...

*Related*