Prime number algorithms

Let us begin with the definition of a Prime number.
A number which has only 1, and itself as factors is called a Prime number.

The simplest problem that one can try is to check if a given number is a prime or not.
If we find that the factors of the given number are just 1, and the number itself, we can call it as a prime number.

How do we find the factors of a given number N?
The most basic approach is to iterate through the numbers from 1 to N and see if each one of them evenly divides N (remainder 0).

Here is the python implementation for the above algorithm.

for f in range(1, n+1): 
	if n % f == 0:
		print(f)

Note: Since 1 and N will always be factors of any number, we need not check them explicitly. I have included them in the algorithm just for the sake of simplicity.

In the above algorithm, when we check if a number f evenly divides n, we can always find another factor f' which is the multiplier of f. i.e (n / f)

For example, while finding the factors of 16, when we verify that 2 is a factor, you can also identify 8 as another factor because 2 * 8 = 16

To find the factors of N, we need not search for factors from 1 to N, but it is enough to search till square root of N.

Here is the python implementation of the improved algorithm.

for f in range(1, int(math.sqrt(num)) + 1):
    if num % f == 0:
        print(f)
        m = int(num / f)
        if m != f:  # To avoid duplicate factors
            print(m) 

To check if a number N is prime, we can verify that there is no factor in the range (2, square root(N))
This is also called trial division method as we are trying to check for all the possible factors.

Following is the Python function to check if a number is a prime or not.

def is_prime(num):
    if num < 2:
        return False
    for f in range(2, int(math.sqrt(num)) + 1):
        if num % f == 0:
            return False
    return True

Another interesting problem is to find the prime factors of a given number. This is based on the fact that any positive number can be represented as the product of unique set of prime numbers. This process is called prime factorization in Number theory.

For example, 28 can be represented as 2 * 2 * 7
66 can be represented as 2 * 3 * 11

There are many algorithms of varying complexities for prime factorization, but we are going to discuss a simple algorithm based on trial division.

def prime_factors(num):
    factors = []
    factor = 2
    while factor * factor <= num:
        while num % factor == 0:
            num = num // factor
            factors.append(factor)
        factor += 1

    if num > 1:
        factors.append(num)
    return factors