Primes are the atoms of arithmetic
A prime is a whole number greater than 1 whose only divisors are 1 and itself: 2, 3, 5, 7, 11, 13 and so on forever. Everything else is composite, meaning it can be written as a product of smaller whole numbers.
The fundamental theorem of arithmetic makes this precise and useful. Every integer greater than 1 is either prime or a product of primes, and that product is unique apart from the order you write it in. There is exactly one way to build 360 out of primes: 2 × 2 × 2 × 3 × 3 × 5, usually written 23 × 32 × 5. No other combination of primes multiplies to 360.
Uniqueness is why 1 is not counted as a prime, a decision that looks arbitrary until you see what admitting it would cost. If 1 were prime, then 360 could also be written 1 × 23 × 32 × 5, and 12 × 23 × 32 × 5, and so on without limit. Uniqueness would collapse, and with it every theorem built on it.
Once you have the factorisation, a great deal follows almost for free. Whether one number divides another, the greatest common divisor of a pair, the least common multiple, whether a number is a perfect square, how many divisors it has, what those divisors sum to — all are read off the exponents rather than computed from scratch.
Trial division, and what the exponents give you
The method is the obvious one, made efficient by two observations. Start with the smallest prime, 2, and divide as many times as it goes in exactly. Move to 3, then 5, 7, 9, 11 — you can step through odd numbers rather than testing primality, because any composite trial divisor will already have had its prime parts removed. Stop when the trial divisor exceeds the square root of what remains.
That stopping rule is the key economy, and it is worth understanding rather than memorising. If a number m has a divisor larger than √m, then the matching cofactor is smaller than √m and would already have been found. So once d² exceeds the remaining quotient, whatever is left must itself be prime. Factorising a trillion needs trial divisors only up to a million rather than up to a trillion.
With the factorisation n = p₁e₁ · p₂e₂ … in hand, four standard quantities follow directly:
Number of divisors: multiply each exponent plus one. A divisor of 360 is built by choosing how many 2s (0, 1, 2 or 3), how many 3s (0, 1 or 2) and how many 5s (0 or 1). That is 4 × 3 × 2 = 24 independent choices, and each gives a different divisor.
Sum of divisors: multiply the geometric series for each prime. For 360 that is (1+2+4+8)(1+3+9)(1+5) = 15 × 13 × 6 = 1,170. Expanding those brackets produces every divisor exactly once, which is why it works.
Euler's totient φ(n) counts the integers from 1 to n that share no factor greater than 1 with n. Multiply n by (1 − 1/p) for each distinct prime: 360 × ½ × ⅔ × ⅖ = 96. This is the quantity RSA encryption is built on.
Perfect squares are exactly the numbers whose exponents are all even, since a square root halves every exponent. 900 = 22 × 32 × 52 is a square; 360 is not, because the 2 and the 5 have odd exponents.
Worked example: factorising 360 and reading off its properties
Run the ladder. Divide by the smallest prime that goes in, and keep going with the quotient.
- 360 ÷ 2 = 180
- 180 ÷ 2 = 90
- 90 ÷ 2 = 45. Now 45 is odd, so 2 is finished — it went in three times.
- 45 ÷ 3 = 15
- 15 ÷ 3 = 5. Three went in twice.
- 5 is not divisible by 3, and 3² = 9 already exceeds 5, so 5 is prime and the ladder stops.
Collecting the divisors used: 360 = 23 × 32 × 5. Check by multiplying back: 8 × 9 × 5 = 360.
Divisor count. Exponents are 3, 2 and 1. Add one to each and multiply: 4 × 3 × 2 = 24 divisors. You can list them if you doubt it: 1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, 18, 20, 24, 30, 36, 40, 45, 60, 72, 90, 120, 180, 360 — twenty-four of them.
Sum of divisors. (1 + 2 + 4 + 8) × (1 + 3 + 9) × (1 + 5) = 15 × 13 × 6 = 1,170. Since that includes 360 itself, the proper divisors sum to 810, which is more than 360 — making 360 an abundant number.
Totient. The distinct primes are 2, 3 and 5, so φ(360) = 360 × (1 − ½) × (1 − ⅓) × (1 − ⅕) = 360 × ½ × ⅔ × ⅖ = 180 × ⅔ × ⅖ = 120 × ⅖ = 96.
Using it on a second number. Factorise 84 = 22 × 3 × 7. The greatest common divisor of 360 and 84 takes the lower exponent of each shared prime: 22 × 31 = 12. The least common multiple takes the higher exponent of every prime that appears in either: 23 × 32 × 5 × 7 = 2,520. Check the identity gcd × lcm = 12 × 2,520 = 30,240, and 360 × 84 = 30,240 as well.
What the shape of a factorisation tells you
A single prime with exponent 1 means the number is prime. Many distinct primes with small exponents means the number has a lot of divisors relative to its size — this is why 360, 720 and 5,040 turn up constantly in timekeeping, geometry and old measurement systems: they are cheap to divide evenly. A single prime with a large exponent means the opposite: 1,024 = 210 is a much larger number than 360 with only 11 divisors against 24.
The largest prime factor is a useful size signal in its own right. A number whose largest prime factor is small relative to the number is called smooth, and smooth numbers are the ones that factor quickly and appear in fast algorithms. A number that is the product of two large primes is the opposite: easy to build, hard to take apart, which is precisely the asymmetry RSA public-key cryptography relies on.
That asymmetry also sets this calculator's practical ceiling. Trial division needs about √n operations, so a twelve-digit number costs up to a million tests, which is instant. A forty-digit semiprime would need 1020 tests and is out of reach for this method entirely — serious factorisation uses Pollard's rho, the elliptic-curve method or the number field sieve instead.
Two quick checks are worth carrying in your head. A number is divisible by 3 exactly when its digits sum to a multiple of 3, and by 9 when they sum to a multiple of 9 — the digits of 360 sum to 9, so both apply. A number ends in 0 or 5 exactly when 5 divides it. Together with the obvious test for 2, those cover the three smallest primes and strip most numbers down quickly.
Factorisations and the quantities that follow from them
| n | Prime factorisation | d(n) | σ(n) | φ(n) |
|---|---|---|---|---|
| 12 | 2² × 3 | 6 | 28 | 4 |
| 28 | 2² × 7 | 6 | 56 | 12 |
| 36 | 2² × 3² | 9 | 91 | 12 |
| 60 | 2² × 3 × 5 | 12 | 168 | 16 |
| 64 | 26 | 7 | 127 | 32 |
| 72 | 2³ × 3² | 12 | 195 | 24 |
| 97 | 97 | 2 | 98 | 96 |
| 100 | 2² × 5² | 9 | 217 | 40 |
| 120 | 2³ × 3 × 5 | 16 | 360 | 32 |
| 360 | 2³ × 3² × 5 | 24 | 1,170 | 96 |
| 1,024 | 210 | 11 | 2,047 | 512 |
The 28 row is a perfect number: its proper divisors 1, 2, 4, 7 and 14 sum to 28, which is why σ(28) = 56 is exactly twice the number. Only a handful of perfect numbers are known below a trillion.
Where factorisations go wrong
- Stopping at composite factors. Writing 360 = 8 × 45 is a correct factorisation but not a prime one. Keep splitting until every factor is prime.
- Treating 1 as a prime factor. It divides everything and contributes nothing, and including it would break the uniqueness the whole theorem rests on.
- Losing an exponent. 2 × 2 × 2 is 2³, not 2². Count the divisions in the ladder rather than reconstructing them afterwards.
- Trial-dividing past the square root. Once the trial divisor squared exceeds the remaining quotient, the quotient is prime and you are finished. Continuing wastes time and adds nothing.
- Confusing gcd with lcm rules. The greatest common divisor takes the lower exponent of each shared prime; the least common multiple takes the higher exponent of every prime present in either number.
- Expecting this to scale to cryptographic sizes. Trial division is fine to about twelve digits. Numbers with two large prime factors are deliberately built to defeat it, and defeating them needs an entirely different algorithm.
What prime factorisation is used for
The most everyday use is fraction arithmetic. Reducing a fraction means cancelling the primes common to numerator and denominator, which is what the greatest common factor calculator computes and the simplifying fractions calculator applies. Adding fractions needs a common denominator, and the smallest one is the least common multiple of the two denominators — again read straight off the exponents.
Simplifying radicals is the same operation in another guise: √360 = √(2³ × 3² × 5) = 6√10, because each pair of identical primes comes out from under the radical. The square root calculator handles the numeric side, and the exponent test tells you in advance whether the root will be whole. Exponent arithmetic more generally is the exponent calculator's territory, and the number of digits in a large power comes from its logarithm.
In computing, factorisation underlies hash table sizing, cycle detection and the choice of moduli; representing those numbers in other bases is the number base conversion calculator's job, and a number's factorisation into powers of 2 is exactly what its binary trailing zeros record.
And in cryptography, the difficulty of the reverse operation is the point. Multiplying two 300-digit primes takes microseconds; recovering them from the product is beyond any known method in reasonable time. Every RSA key in use depends on that gap, and on Euler's totient, which this calculator reports.