Prime Factorization Calculator
Prime Factorization
--
Number of Prime Factors
--
Total Number of Divisors
--
How Prime Factorization Works
Prime factorization is the process of expressing a positive integer as a product of prime numbers. A prime number is a natural number greater than 1 that has no positive divisors other than 1 and itself. The Fundamental Theorem of Arithmetic, first proven by Euclid around 300 BCE and later rigorously formalized by Carl Friedrich Gauss in 1801, guarantees that every integer greater than 1 has a unique prime factorization (up to the order of factors).
For example, 360 = 23 × 32 × 5. No other combination of prime numbers multiplies to give 360. This uniqueness is not just an abstract property -- it is the foundation of modern cryptography, number theory, and computer science. The National Institute of Standards and Technology (NIST) bases the RSA encryption standard on the computational difficulty of factoring large numbers: while multiplying two 300-digit primes takes milliseconds, factoring their product back into those primes could take longer than the age of the universe with current technology.
The trial division algorithm used by this calculator works by dividing the input number by the smallest prime (2) repeatedly, then trying 3, 5, 7, and so on up to the square root of the remaining quotient. If any number remains after this process, it must be prime itself. This method is efficient for numbers up to about 1012. For larger numbers, more sophisticated algorithms like the Quadratic Sieve or General Number Field Sieve are used. Use our Divisibility Calculator to check if specific numbers divide evenly.
The Prime Factorization Algorithm
Trial division follows a systematic process. The algorithm is guaranteed to produce the unique prime factorization for any positive integer.
Step 1: Start with the smallest prime divisor d = 2
Step 2: While d × d ≤ n: if d divides n evenly, record d as a factor and divide n by d. Otherwise, increment d.
Step 3: If n > 1 after the loop, n itself is a prime factor
Key insight: You only need to test divisors up to √n, because if n = a × b and both a, b > √n, then a × b > n -- a contradiction.
Worked example: Factor 360. Divide by 2: 360/2 = 180, 180/2 = 90, 90/2 = 45 (2 no longer divides). Divide by 3: 45/3 = 15, 15/3 = 5 (3 no longer divides). 5 is prime and greater than √5, so it is the last factor. Result: 360 = 23 × 32 × 51.
Key Terms You Should Know
- Prime number -- a natural number greater than 1 whose only factors are 1 and itself. The first ten primes are 2, 3, 5, 7, 11, 13, 17, 19, 23, 29. Note that 2 is the only even prime.
- Composite number -- a positive integer greater than 1 that is not prime. It has at least one factor besides 1 and itself. The first composites are 4, 6, 8, 9, 10, 12.
- Fundamental Theorem of Arithmetic -- the theorem stating that every integer > 1 can be written as a unique product of primes (up to ordering). First proven by Euclid.
- Divisor (factor) -- a number that divides another number evenly. The divisors of 12 are 1, 2, 3, 4, 6, 12.
- Multiplicity -- the number of times a prime appears in the factorization. In 360 = 23 × 32 × 5, the prime 2 has multiplicity 3.
Prime Factorizations of Common Numbers
The following table shows prime factorizations for commonly referenced numbers, along with their total divisor count. The divisor count formula is: if n = p1a1 × p2a2 × ..., then the number of divisors = (a1+1)(a2+1)...
| Number | Prime Factorization | Total Divisors | Context |
|---|---|---|---|
| 12 | 2² × 3 | 6 | Dozen, clock hours |
| 60 | 2² × 3 × 5 | 12 | Seconds/minutes, degrees |
| 100 | 2² × 5² | 9 | Percentages, centimeters |
| 360 | 2³ × 3² × 5 | 24 | Degrees in a circle |
| 1000 | 2³ × 5³ | 16 | Metric kilo- prefix |
| 1024 | 210 | 11 | Computing: 1 KB |
| 5040 | 24 × 3² × 5 × 7 | 60 | 7! = 5040 (highly composite) |
Practical Applications
Finding GCD and LCM. Prime factorization provides the most reliable method for computing the greatest common divisor (GCD) and least common multiple (LCM) of two numbers. For 360 and 450: 360 = 23 × 32 × 5 and 450 = 2 × 32 × 52. GCD = 2min(3,1) × 3min(2,2) × 5min(1,2) = 2 × 9 × 5 = 90. LCM = 2max(3,1) × 3max(2,2) × 5max(1,2) = 8 × 9 × 25 = 1,800. Use our Fraction Calculator which uses GCD internally to simplify fractions.
Simplifying fractions. To simplify 84/126, factor both: 84 = 22 × 3 × 7 and 126 = 2 × 32 × 7. Cancel common factors (2, 3, and 7): 84/126 = (2 × 2 × 3 × 7)/(2 × 3 × 3 × 7) = 2/3.
Cryptography and security. RSA encryption, used to secure internet communications, relies on the difficulty of factoring the product of two large primes. The NIST currently recommends RSA key sizes of 2048 bits or larger (the product of two ~1024-bit primes, each roughly 308 decimal digits). Factoring such numbers is computationally infeasible with current classical computers, though quantum computers using Shor's algorithm could theoretically do it in polynomial time -- which is why NIST is developing post-quantum cryptography standards.
Tips for Prime Factorization
- Always start with the smallest prime (2). Divide out all factors of 2 first (check if the number is even), then try 3, 5, 7, etc. This systematic approach ensures you do not miss any factors.
- Use divisibility rules as shortcuts. A number is divisible by 2 if it is even, by 3 if its digit sum is divisible by 3, by 5 if it ends in 0 or 5, and by 11 if the alternating digit sum is divisible by 11.
- Stop testing at the square root. If no prime up to √n divides n, then n is prime. For example, to check if 97 is prime, you only need to test primes up to √97 ≈ 9.8 (i.e., 2, 3, 5, 7). None divide 97, so it is prime.
- Use factorization to count divisors. The divisor count formula (a1+1)(a2+1)... provides the total number of positive divisors without listing them all. This is far more efficient for large numbers.
- Remember that 1 is not prime. By convention and mathematical definition, 1 is neither prime nor composite. This convention ensures the uniqueness of prime factorization, since including 1 as a prime would allow infinitely many representations (e.g., 6 = 2 × 3 = 1 × 2 × 3 = 1 × 1 × 2 × 3...).
Prime Numbers in Mathematics
Euclid proved around 300 BCE that there are infinitely many prime numbers, using an elegant proof by contradiction that remains a cornerstone of mathematical reasoning. As of 2024, the largest known prime is 2136,279,841 − 1, a Mersenne prime with over 41 million digits, discovered by the Great Internet Mersenne Prime Search (GIMPS) project. Mersenne primes have the form 2p − 1 where p is itself prime, though not all such values are prime.
The Prime Number Theorem, proved independently by Hadamard and de la Vallee Poussin in 1896, states that the number of primes less than n is approximately n/ln(n). Among the first million positive integers, there are 78,498 primes (about 7.85%). Among the first billion, there are 50,847,534 primes (about 5.08%). The density of primes decreases slowly but never reaches zero -- primes become rarer but never run out. The distribution of primes is connected to the Riemann Hypothesis, one of the seven Millennium Prize Problems with a $1 million reward for a proof.
Frequently Asked Questions
Why is prime factorization unique?
The Fundamental Theorem of Arithmetic guarantees that every integer greater than 1 has exactly one prime factorization, up to the order of factors. This was first proven by Euclid around 300 BCE and rigorously formalized by Gauss in 1801. For example, 60 can only be written as 22 × 3 × 5 -- no other combination of primes produces 60. This uniqueness is not just a theoretical curiosity: it is the foundation of the RSA encryption algorithm, the divisor-counting formula, and the methods for computing GCD and LCM from prime factorizations.
How do you find the total number of divisors from a prime factorization?
From the prime factorization n = p1a1 × p2a2 × ..., the total number of positive divisors is (a1+1)(a2+1)... For 360 = 23 × 32 × 51, the divisor count is (3+1)(2+1)(1+1) = 4 × 3 × 2 = 24. This works because each divisor of 360 must be of the form 2i × 3j × 5k where 0 ≤ i ≤ 3, 0 ≤ j ≤ 2, and 0 ≤ k ≤ 1. The number of choices for each exponent multiplies together.
What is the largest known prime number?
As of 2024, the largest known prime is 2136,279,841 − 1, a Mersenne prime with 41,024,320 digits. It was discovered on October 12, 2024, by the Great Internet Mersenne Prime Search (GIMPS), a distributed computing project. Mersenne primes (primes of the form 2p − 1) are the easiest large primes to find because the Lucas-Lehmer primality test is extremely efficient for this specific form. As of 2024, only 52 Mersenne primes have been found.
Why is 1 not considered a prime number?
By modern mathematical convention, 1 is neither prime nor composite. The primary reason is to preserve the uniqueness of prime factorization. If 1 were prime, then 6 could be written as 2 × 3, or 1 × 2 × 3, or 1 × 1 × 2 × 3, and so on -- destroying the "unique" in the Fundamental Theorem. Historically, some mathematicians did consider 1 prime, but the modern definition (a prime must have exactly two distinct positive divisors: 1 and itself) excludes 1 because it has only one positive divisor. This convention is universal in contemporary mathematics.
How is prime factorization used in cryptography?
RSA encryption, the most widely used public-key cryptosystem, relies on the fact that multiplying two large primes is easy but factoring their product is computationally infeasible. NIST recommends RSA keys of 2048 bits (products of two ~1024-bit primes). To generate an RSA key, you select two large random primes p and q, compute n = p × q, and publish n as part of the public key. Anyone can encrypt using n, but only someone who knows p and q can decrypt efficiently. The security of trillions of dollars in online transactions depends on this asymmetry between multiplication and factoring.
How many prime numbers are there below 1,000?
There are exactly 168 prime numbers below 1,000. The Prime Number Theorem provides an approximation: the count of primes below n is approximately n/ln(n). For n = 1000, this gives 1000/6.908 = 145, which underestimates the actual 168 but improves in accuracy for larger n. Below 10,000 there are 1,229 primes (12.3%); below 1,000,000 there are 78,498 (7.85%); below 1,000,000,000 there are 50,847,534 (5.08%). Primes thin out but never disappear, as Euclid proved over 2,300 years ago. Use our Prime Number Calculator to check if a specific number is prime.