What is a prime number?
A prime number is a whole number greater than 1 whose only positive divisors are 1 and itself. The first few are 2, 3, 5, 7, 11, 13 and 17. A number with more divisors than that is called composite. The number 2 is the only even prime, and 1 is neither prime nor composite.
What is prime factorization?
The fundamental theorem of arithmetic says every whole number greater than 1 is either prime or can be written as a product of primes, and that product is unique apart from the order of the factors. For example, 60 = 5 × 3 × 2 × 2, and no other collection of primes multiplies to 60. Writing repeated primes with exponents gives the compact form 22 × 3 × 5.
Method 1: trial division
Divide by the smallest prime that goes in evenly, then repeat on the quotient until you reach 1. Here is 820:
| Step | Result |
|---|---|
| 820 ÷ 2 | 410 |
| 410 ÷ 2 | 205 |
| 205 ÷ 5 | 41 |
| 41 ÷ 41 | 1 |
So 820 = 2 × 2 × 5 × 41 = 22 × 5 × 41. You can stop trial dividing once the next prime squared is bigger than what remains, because the remainder must then itself be prime. Here 41 is smaller than 7 squared (49), so after 2, 3, 5 fail to give a further split, 41 is declared prime.
Method 2: the factor tree
Split the number into any two factors, then split each of those, until every leaf is prime. The branches can differ (820 can start as 2 × 410 or as 4 × 205), but the leaves always come out the same: 2, 2, 5 and 41. This calculator draws the tree by peeling off the smallest prime at each level.
How to check whether a number is prime
Try dividing by every prime up to the square root of the number. If none divides it evenly, the number is prime. To test 97, the square root is just under 10, so you only need to try 2, 3, 5 and 7. None works, so 97 is prime. For very large numbers the calculator switches to a faster probabilistic test that is deterministic for numbers of this size.
Common prime factorizations
| Number | Prime factorization |
|---|---|
| 12 | 22 × 3 |
| 36 | 22 × 32 |
| 60 | 22 × 3 × 5 |
| 100 | 22 × 52 |
| 360 | 23 × 32 × 5 |
| 1,000 | 23 × 53 |
Why it matters
- It gives the greatest common factor and least common multiple of any set of numbers by comparing exponents.
- It counts divisors: add one to each exponent and multiply. For 360 that is 4 × 3 × 2 = 24 divisors.
- Modern public-key encryption relies on the fact that multiplying two huge primes is easy while recovering them from the product is hard.
Tips
If the last digit is even, 2 is a factor; if the digits add to a multiple of 3, so is 3; if the last digit is 0 or 5, so is 5. Spotting these quickly speeds up any manual factorization.
Reading the results
The first line shows the factorization with every prime repeated, the way a factor tree ends. The second line shows the compact exponent form, where a caret means a power. The distinct count tells you how many different primes appear, and the repeated count tells you how many leaves a factor tree would have. For 820 those counts are 3 and 4.
Using the factorization
With two factorizations side by side you can read off both the GCF (smallest exponent of each shared prime) and the LCM (largest exponent of every prime). You can also tell instantly whether a number is a perfect square, since every exponent will be even, or a perfect cube, where every exponent is a multiple of three. For example 3,600 = 24 × 32 × 52 is a perfect square, and its square root is 22 × 3 × 5 = 60.