Prime Factorization
Check whether a number is prime and split it into its prime factors.
Any whole number up to 9,007,199,254,740,991 (253 − 1).
Composite number (not prime)
360 = 23 × 32 × 5
- Number of divisors
- 24
- Sum of divisors
- 1,170
- Previous prime
- 359
- Next prime
- 367
Division ladder
| 2 | 360 |
|---|---|
| 2 | 180 |
| 2 | 90 |
| 3 | 45 |
| 3 | 15 |
| 5 | 5 |
| 1 |
All 24 divisors
1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, 18, 20, 24, 30, 36, 40, 45, 60, 72, 90, 120, 180, 360
How a number is split into primes
A prime number is a whole number greater than 1 that can only be divided by 1 and by itself: 2, 3, 5, 7, 11, 13 and so on. Every other whole number above 1 is composite, meaning it is a product of smaller numbers. Keep splitting those and you always end at primes, and always at the same ones. That is the fundamental theorem of arithmetic: every whole number above 1 is a product of primes in exactly one way, apart from the order of the factors.
The tool finds them by trial division. It divides by 2 as often as that goes, then by 3, then by 5, 7, 11 and upwards, each time carrying on with what is left. For 360 that gives 360 ÷ 2 = 180, 180 ÷ 2 = 90, 90 ÷ 2 = 45, then 45 ÷ 3 = 15 and 15 ÷ 3 = 5, which is prime. Three twos, two threes and a five: 360 = 23 × 32 × 5. The division ladder shows these steps for your own number.
Where the search can stop
Divisors come in pairs. If 221 = a × b, the smaller of the two cannot be more than √221, which is about 14.9, so only the primes up to 13 need trying. 2, 3, 5, 7 and 11 leave a remainder; 13 goes in exactly 17 times. So 221 = 13 × 17. Had 13 failed as well, 221 would have been prime.
Two shortcuts keep this quick. Candidates that are multiples of 2 or 3 are skipped. And before a long search starts, the tool checks whether what is left is already prime, with the Miller-Rabin test, using the twelve primes from 2 to 37 as bases. With those bases the test is proven correct for every number below 264, so "prime" on this page is certain, not probable. The previous and the next prime are found with the same test.
Why 1 is not a prime
Mostly so that the theorem above stays true. If 1 were prime, 6 could be written as 2 × 3, as 1 × 2 × 3 and as 1 × 1 × 2 × 3, and "exactly one way" would be gone. The definition therefore asks for exactly two divisors, and 1 has only one. Zero is left out too, because every number divides it. Neither 0 nor 1 is prime or composite.
Numbers that look prime
2 is prime, and it is the only even prime. Odd numbers below 100 that are easily taken for primes are 51 (3 × 17), 57 (3 × 19), 87 (3 × 29) and 91 (7 × 13). The first three give themselves away because their digits add up to a multiple of 3.
Counting the divisors
Every divisor is built from the prime factors. For 360 = 23 × 32 × 5 you can use the 2 from zero to three times, the 3 from zero to two times and the 5 once or not at all, which makes 4 × 3 × 2 = 24 divisors. Their sum follows the same pattern: (1 + 2 + 4 + 8) × (1 + 3 + 9) × (1 + 5) = 1,170. That sum includes 360 itself.
Limits
The largest number accepted is 9,007,199,254,740,991 (253 − 1). Beyond it the ordinary numbers of JavaScript, which do the dividing here, are no longer exact.
Most numbers are split at once. The slow ones are products of two large primes of about the same size, such as 9,007,195,909,437,503 = 94,906,247 × 94,906,249. For that one about 30 million divisors have to be tried, and you may notice a short pause. RSA encryption relies on the same difficulty: multiplying two primes of 300 digits is instant, but nobody knows a practical way to get them back from the product.
A negative number is factored as the same number without its minus sign.