# Prime Factorisation

## Given a natural number `n`, find its prime factorisation

`17160 = 2*2*2*3*5*11*13`
`Shrinking n    Prime Factorisation420/2 = 210            420 = 2*210210/2 = 105            420 = 2*2*105105/2 = not divisible105/3 = 35             420 = 2*2*3*3535/3  = not divisible35/4  = not divisible35/5  = 7              420 = 2*2*3*5*77/5   = not divisible7/6   = not divisible7/7   = 1`
`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`
1. 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)`.
`#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);}`

Hi! 👋 I’m Mike — did you know the oldest computer was owned by Adam and Eve? It was an apple with very limited memory. Just one byte and everything crashed.

## More from Mike Nöthiger

Hi! 👋 I’m Mike — did you know the oldest computer was owned by Adam and Eve? It was an apple with very limited memory. Just one byte and everything crashed.

## Linear Algebra Operations with PyTorch

Get the Medium app