# Prime Factorisation

## Given a natural number `n`

, find its prime factorisation

Each natural number is composed of a unique product of indivisible numbers also called prime numbers. Prime numbers are the building blocks of natural numbers and the prime factorisation of a number is its unique fingerprint. The prime factorisation of 17'160 is:

`17160 = 2*2*2*3*5*11*13`

It is easy to validate a given finger print by multiplying the numbers together. It is rather hard to calculate the finger print of a given number. There is no simple operation like multiplication to receive the sequence of numbers in the prime factorisation. Still we know it must exist and the smallest possible number in this sequence is `2`

. Based on those facts we can work out an algorithm to receive the finger print of a given number `n`

.

**Idea:** Break out the smallest indivisible factor (`2`

) of a given number `n`

as often as possible, then repeat for the next bigger number up to `n`

. Evolutionary, every number that can be extracted is a prime number, the sequence of numbers extracted will be the prime factorisation of `n`

.

(slight performance improvements will be added to above idea, it should give a rather general understanding of the concept).

**Example: **`n=420`

**Shrinking n** **Prime Factorisation**

420/2 = 210 420 = 2*210

210/2 = 105 420 = 2*2*105

105/2 = not divisible

105/3 = 35 420 = 2*2*3*35

35/3 = not divisible

35/4 = not divisible

35/5 = 7 420 = 2*2*3*5*7

7/5 = not divisible

7/6 = not divisible

7/7 = 1

Prime factorisation of `420`

is `2*2*3*5*7`

. Automatically, every number that divides the shrinking `n`

can be considered prime, because we start with the smallest prime `2`

and eliminate it completely from `n`

. Consequently, we can be certain that the prime factorisation of the remaining `n`

(105) does not contain any `2`

’s at all, thus can’t be divided by `2`

or any multiple of it. It will simply never happen that `n`

will be divided by a composite number (a number that can be further divided) because the prime factorisation of the composite number consists only of numbers smaller than itself, and these numbers were evolutionary eliminated from the shrinking `n`

. It’s way easier to understand this by showing `420`

in its prime factorisation in the above divisions:

**2***2*3*5*7/**2**

**2***3*5*7/**2**

**3***5*7/**3**

5*7/4 not divisible

**5***7/**5**

7/6 not divisible

**7**/**7**

*Even though **420** was initially divisible by **4**, the remaining **n** (5*7) is not because we eliminated all **2**’s from the prime factorisation of the remaining n which is a good thing, because **4** would not be prime. **6** would also divide **420**, but neither will it divide the remaining **n** (7) since it’s a multiple of **2*3** which were both previously eliminated.*

Of course the prime factorisation is initially concealed, above example is a demonstration why divisions will only ever happen by prime numbers.

The computational cost would be O(n) in worst case; if `n`

has no divider at all (i.e. is prime), which means we would divide `n`

by all numbers from `1...n`

(since `n`

doesn’t shrink). The computational cost can be reduced using the following facts:

- After
`2`

has been eliminated, divisions by even numbers can be omitted, because even numbers are all divisible by`2`

and… yeah you get it (btw.`2`

is the only even prime number and the reason for that is…`2`

). This cuts computational costs in half since only odd numbers need to be checked. - Let
`a`

be a number bigger than`sqrt(n)`

. If`a`

divides`n`

it must have a partner`b`

below`sqrt(n)`

, otherwise`a*b > n`

. This means`b`

would have been detected as we went through the numbers below`sqrt(n)`

, we can therefore safely stop dividing as we arrive at`sqrt(n)`

.

Please note, that `n`

shrinks, every time a divisor has been detected, which implies `sqrt(n)`

also gets smaller. The `sqrt(n)`

rule is way more useful in the worst case, where `n`

is prime: If we did not find a divisor below `sqrt(n)`

there will certainly be none above `sqrt(n)`

and we can stop dividing; **n is prime! **🥳

We are now at `sqrt(n)/2`

divisions in the worst case which is in `O(sqrt(n))`

.

Here’s an example program that prints the prime factorisation of `n`

:

`#include <stdio.h>`

#include <math.h>

long n = 420;

long i;

int main() {

// find even divisors O(log n)

while (n % 2 == 0) {

printf("2 "); // prime factor found!

n /= 2;

}

// find odd divisors O(sqrt(n))

i = 3;

while (i < sqrt(n) + 1) {

if (n % i == 0) {

printf("%ld ", i); // prime factor found!

n /= i;

} else {

i += 2;

}

}

// if the remaining n could not be divided to 1

// then the remaining n is prime itself. This is

// also where we'll end up if n is a prime number.

if (n > 1) printf("%ld ", n);

}