Prime Factorization
Break any whole number into its prime factor building blocks.
A prime number is a natural number greater than 1 that has no divisors other than 1 and itself. Primes are the fundamental building blocks of all integers — every integer > 1 is either prime or can be uniquely factored into primes (Fundamental Theorem of Arithmetic).
Tip: Quick primality checks: if a number ends in 0, 2, 4, 5, 6, 8 — it's not prime (except 2 and 5). Then check divisibility by 3 (digit sum divisible by 3) and 7. If it passes all these, it's likely prime if it's under 200.
- 1Trial division: test if n is divisible by any integer from 2 to √n
- 2If no divisor found, n is prime
- 3Sieve of Eratosthenes: efficiently finds all primes up to a limit
- 4For large numbers, probabilistic tests like Miller-Rabin are used
| Range | Primes |
|---|---|
| 1–20 | 2, 3, 5, 7, 11, 13, 17, 19 |
| 21–50 | 23, 29, 31, 37, 41, 43, 47 |
| 51–80 | 53, 59, 61, 67, 71, 73, 79 |
| 81–100 | 83, 89, 97 |
Fun Fact
RSA encryption — used to secure most internet traffic including HTTPS — relies on the fact that multiplying two large primes is easy, but factoring the result back is computationally infeasible. The security of your bank's website depends on prime numbers.
References