Prime Factorization
Decompose any whole number up to 1018 into its prime factors, exactly. Also gives the number and sum of divisors, Euler’s totient φ(n) and a factor tree.
What is Prime Factorization?
A prime is a whole number greater than 1 whose only divisors are 1 and itself: 2, 3, 5, 7, 11, … The fundamental theorem of arithmetic says every whole number ≥ 2 can be written as a product of primes in exactly one way (apart from order).
The factorization unlocks everything else about a number: all its divisors, its GCD and LCM with other numbers, and Euler’s totient — the backbone of RSA encryption, whose security rests on how hard it is to factor very large numbers.
Factor Tree
360Divisibility Rules
| By | n is divisible when… |
|---|---|
| 2 | the last digit is even |
| 3 | the digit sum is divisible by 3 |
| 4 | the last two digits form a multiple of 4 |
| 5 | the last digit is 0 or 5 |
| 6 | it is divisible by both 2 and 3 |
| 7 | 2×(last digit) subtracted from the rest is a multiple of 7 |
| 8 | the last three digits form a multiple of 8 |
| 9 | the digit sum is divisible by 9 |
| 11 | the alternating digit sum is divisible by 11 |
Methods & Formulas
Divide by each prime in turn as often as it goes. You can stop at √n: whatever is left above 1 must itself be prime.
Each divisor picks an exponent from 0 to ai for every prime, so multiply the number of choices.
Counts the numbers from 1 to n that share no factor with n. It is the key ingredient of RSA public-key cryptography.
Sources & Verification
- K. H. Rosen, Elementary Number Theory and Its Applications, 6th ed., Pearson, 2011 — Ch. 3 (Primes and Greatest Common Divisors) and Ch. 7 (Multiplicative Functions: the Euler phi-function, the sum and number of divisors).
- G. H. Hardy & E. M. Wright, An Introduction to the Theory of Numbers, 6th ed., Oxford University Press, 2008 — Ch. XVI (The Arithmetical Functions φ(n), μ(n), d(n), σ(n), r(n)).