Prime factorization calculator

Divide by the smallest prime that goes in, and repeat on the quotient until it reaches 1. For 360: 360 ÷ 2 = 180, ÷ 2 = 90, ÷ 2 = 45, ÷ 3 = 15, ÷ 3 = 5, and 5 is prime, so 360 = 2³ × 3² × 5. Only primes up to the square root of what is left need testing; if none divides it, the remainder is itself prime.

No. A prime has exactly two divisors, 1 and itself, and 1 has only one. Excluding 1 keeps factorizations unique: if 1 counted as prime, 6 could be written as 2 × 3, 1 × 2 × 3, 1 × 1 × 2 × 3 and so on. 1 is neither prime nor composite, and 2 is the smallest prime and the only even one.

Add 1 to each exponent and multiply. 360 = 2³ × 3² × 5¹, so it has (3 + 1)(2 + 1)(1 + 1) = 24 divisors, because each divisor uses 0 to 3 twos, 0 to 2 threes and 0 or 1 five. The sum of the divisors is a similar product: σ(360) = (2⁴ − 1)/1 × (3³ − 1)/2 × (5² − 1)/4 = 15 × 13 × 6 = 1,170.

Trial division up to √n is far too slow for 20-digit numbers, so the Miller–Rabin test checks a handful of bases instead. Below 3.3 × 10²⁴, passing with the first 13 primes (2 to 41) as bases proves primality (Sorenson and Webster, 2015). 2⁶¹ − 1 = 2,305,843,009,213,693,951 passes and is prime; 2⁶⁷ − 1 fails and equals 193,707,721 × 761,838,257,287.

RSA encryption relies on multiplying two large primes being quick while factoring their product is impractically slow. NIST SP 800-57 rates a 2048-bit RSA modulus, about 617 decimal digits, as giving 112 bits of security. That is ten times the 60-digit limit here, and even within that limit Pollard's rho splits a number quickly only when one of its factors is fairly small.

Accuracy depends on your inputs and the method's assumptions. Decimal arithmetic uses 50 significant digits, but estimates, numerical methods and source data can be less precise; the displayed rounding does not remove those limits. It is checked against 6 worked examples whose answers come from independent sources; for example, “360” is checked against Python 3.8 trial division and divisor enumeration (scratchpad forkA/verify.py).

Hardy & Wright, An Introduction to the Theory of Numbers, §2.10 and §16.7 (divisor functions); Sorenson & Webster (2015), Strong pseudoprimes to twelve prime bases; Brent (1980), An improved Monte Carlo factorization algorithm.