Prime factorization calculator and prime checker

Prime factorization and prime checker in one tool

This prime factorization calculator answers two classic questions: is it prime? and what are its prime factors? Type a whole number of up to 40 digits and you get the answer, the method used, the factorization written with powers (such as 2³ × 3² × 5), the number of factors, the full list of factors and the nearest primes on either side. A second mode lists every prime up to 10 million.

How to use it

1. Choose "Check and factor a number", type it in "Whole number" and click "Check" or press Enter. Powers work too: 2^61 − 1.
2. Read the answer, the "Prime factorization", the "Number of factors", the "Previous prime" and the "Next prime". "Repeated division" shows the working.
3. Tick "Show the factor tree" to draw the factor tree, and "Show the list of factors" for every factor and their sum.
4. For a list, choose "List of prime numbers", enter N in "Prime numbers up to N" and click "Show the list". "Download the list (.txt)" saves the whole list, one number per line.

Prime numbers explained

A prime number is a whole number with exactly two factors: 1 and itself. 2, 3, 5, 7, 11 and 13 are prime, and 2 is the only even prime. 1 is not prime, because it has only one factor, and neither is 0. Any whole number above 1 that is not prime is called composite.

To check a number by hand, try dividing it by every whole number from 2 up to its square root. For 97, √97 ≈ 9.8, and none of 2, 3, 5 or 7 divides 97, so 97 is prime. Watch out for 51: it looks prime, but 51 = 3 × 17. For very large numbers this prime number checker uses the Miller-Rabin test, which gives a proven answer for every number up to 2⁶⁴ and well beyond.

How to find the prime factorization

Divide by the smallest prime that goes in exactly, keep going while it still divides, then move on to the next prime. With 2,024: 2,024 ÷ 2 = 1,012, 1,012 ÷ 2 = 506, 506 ÷ 2 = 253, 253 ÷ 11 = 23, 23 ÷ 23 = 1. So 2,024 = 2³ × 11 × 23. Every number has only one prime factorization, apart from the order of the factors. It also tells you how many factors the number has: add 1 to each power and multiply, (3 + 1) × 2 × 2 = 16 factors. The nearest primes are 2,017 and 2,027.

A factor tree shows the same thing as a diagram: each branch splits a number into a prime and what is left, until only primes remain at the ends.

The sieve of Eratosthenes

To list the primes up to N, write out the numbers from 2 to N, keep 2 and cross out its multiples, keep the next number left, 3, and cross out its multiples, and so on. Up to 100 you only need to cross out the multiples of 2, 3, 5 and 7, and 25 primes remain. There are 664,579 primes below 10 million, and the tool lists them in well under a second.

There are infinitely many primes, as Euclid proved more than 2,000 years ago. Some encryption systems rely on the fact that, with known methods, it takes an enormous amount of computing to recover two large primes from their product when they have hundreds of digits.

Frequently asked questions

Why is 1 not a prime number?

A prime must have exactly two different factors, and 1 has only one. Leaving it out also keeps every factorization unique: otherwise 6 could be written 2 × 3, 1 × 2 × 3, 1 × 1 × 2 × 3 and so on.

How big a number can I check?

Up to 40 digits. The prime test is almost instant. Factoring can take longer when the number is the product of two large primes: after 10 seconds the tool stops and shows which factor it could not split.

Is 2⁶¹ − 1 prime?

Yes. 2⁶¹ − 1 = 2,305,843,009,213,693,951 is a Mersenne prime: type 2^61 − 1 to see it. The largest prime below 2⁶⁴ is 18,446,744,073,709,551,557.