Prime Numbers

Anyone that has studied secondary school mathematics knows what a prime number is but just to recap the definition of a prime number is any number which is only divisible by 1 and itself. 1 is however not a prime number as it is only divisible by itself, and other than 2 all prime numbers are odd. From this we can create an algorithm for checking if a number is a prime number. We simple try dividing it by every number up to half it’s value since the factors of a number repeat after this value for example the factors of 10 are:

\begin{aligned}
1 &\times 10 \\
2 &\times 5 \\
5 &\times 2 \\
10 &\times 1  
\end{aligned}

The factors simply repeat i.e.

\begin{aligned}
1 \times 10 &= 10 \times 1 \\
2 \times 5 &= 5 \times 2
\end{aligned}

We will thus create a value for the maximum divisor which will be:

\lfloor  \sqrt{n} \rfloor

This is the floor of the square root of n. From this we can easily create an algorithm to find out if a number is prime:

if n = 1 then
    return False
else if n = 2 then
    return True
else if n>2 and n is even then
    return False
else
    for i=2 and i<=maximum divisor
        if n%i=0 then
            return False
    return True

We can then translate this into a Python program as follows:

def isprime(n):
    max_divisor = math.floor(math.sqrt(n))
    if n == 1:
        return False
    elif n == 2:
        return True
    elif n > 2 and not isodd(n):
        return False
    else:
        for i in range(2, max_divisor+1):
            if(n % i == 0):
                return False
        return True

Note: The way range works in Python we have to add one to max_divisor.

Running this code on values of 10 and 13 results in:

>>> isprime(10)
False
>>> isprime(13)
True

We can now create a program to print all the prime numbers up to a given value, like the Collatz function we will use an array:

def primeseq(n):
    primes = []
    for i in range(1, n):
        if isprime(i):
            primes.append(i)
    return primes

Running this function on values of 10 and 20 gives:

>>> primeseq(10)
[2, 3, 5, 7]
>>> primeseq(20)
[2, 3, 5, 7, 11, 13, 17, 19]