Index / Maths
Prime Factoriser
A whole number into its prime factorisation, with the divisors, Euler's totient, the sum of the divisors, and the greatest common divisor and least common multiple against a second number. Primality is decided, not guessed at.
Number
Whole numbers up to 4,503,599,627,370,496.
Spaces, commas and underscores are ignored.
Leave it empty to skip that section.
Prime factorisation
--
Divisors
--
Distinct primes
--
What the factorisation gives you
Divisors
Against the second number
The limit, the primality test, and the conventions
The limit is 4,503,599,627,370,496, which is 252.
Factorising needs modular multiplication, and this page does that by
doubling and adding rather than in 128-bit arithmetic it does not have.
Every intermediate sum has to stay a whole number in a double, and
doubling a remainder below 252 keeps it under
253, which is the last integer a double counts exactly. A
larger number is refused rather than factorised approximately.
Primality is decided, not estimated. The Miller–Rabin test is used with the bases 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31 and 37. Those bases are known to give the right answer for every number below 3,317,044,064,679,887,385,961,981, which is far above the limit here, so within this page the test is deterministic and “probably prime” never appears.
Composites are split by trial division and then Pollard's rho, in Brent's variant, with the cycle restarted on a different polynomial when it stalls. Rho finds a factor near p½ steps, so the hard case here is a semiprime with two factors around 67 million, and that still lands in a moment.
1 is neither prime nor composite, and its factorisation is the empty product. 0 has no factorisation at all: every number divides it. Both are said rather than shown as a blank.
A negative number is factorised by magnitude, with the sign reported separately. −12 is −1 × 2² × 3; the primes are a property of 12.
σ(n) is the sum of all divisors including n itself, and the aliquot sum leaves n out. A number is perfect when the aliquot sum equals it, abundant when it is larger and deficient when it is smaller. σ is computed on digit strings, because it can exceed what a double counts exactly even when n does not.
φ(n) is Euler's totient: how many numbers from 1 to n share no factor with n. It is computed from the factorisation as ∏pe−1(p−1), which is exact, rather than by counting.
The GCD uses the Euclidean algorithm and the LCM is a × b / gcd, divided before multiplying so that the product never has to exist. Where the LCM would exceed the limit the page says so rather than wrapping round.
Primality is decided, not estimated. The Miller–Rabin test is used with the bases 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31 and 37. Those bases are known to give the right answer for every number below 3,317,044,064,679,887,385,961,981, which is far above the limit here, so within this page the test is deterministic and “probably prime” never appears.
Composites are split by trial division and then Pollard's rho, in Brent's variant, with the cycle restarted on a different polynomial when it stalls. Rho finds a factor near p½ steps, so the hard case here is a semiprime with two factors around 67 million, and that still lands in a moment.
1 is neither prime nor composite, and its factorisation is the empty product. 0 has no factorisation at all: every number divides it. Both are said rather than shown as a blank.
A negative number is factorised by magnitude, with the sign reported separately. −12 is −1 × 2² × 3; the primes are a property of 12.
σ(n) is the sum of all divisors including n itself, and the aliquot sum leaves n out. A number is perfect when the aliquot sum equals it, abundant when it is larger and deficient when it is smaller. σ is computed on digit strings, because it can exceed what a double counts exactly even when n does not.
φ(n) is Euler's totient: how many numbers from 1 to n share no factor with n. It is computed from the factorisation as ∏pe−1(p−1), which is exact, rather than by counting.
The GCD uses the Euclidean algorithm and the LCM is a × b / gcd, divided before multiplying so that the product never has to exist. Where the LCM would exceed the limit the page says so rather than wrapping round.