optimisation / python

is_prime optimisation

— 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

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s