Prime Factorisation

Given a natural number n, find its prime factorisation

Photo by Raphaël Biscaldi on Unsplash

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:

1. 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.
2. 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);
}