Prime Factorisation

Given a natural number n, find its prime factorisation

Photo by Raphaël Biscaldi on Unsplash
17160 = 2*2*2*3*5*11*13
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
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.

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store