Home / Calculators / Prime factorization

Prime factorization with step-by-step trial division

Enter an integer n (|n| ≥ 2) to see every division step, τ(n), σ(n), φ(n), and an automatically drawn factor tree. Supply an optional integer m to compare exponents and derive gcd and lcm.

Other languages: ja | en | zh-CN | es

Inputs

Integers are parsed exactly using BigInt so that large classroom examples are handled safely. Supply a second integer to compare exponents and derive gcd/lcm from the prime factorizations.

Digits with an optional leading minus sign. |n| must be at least 2.

If supplied, the tool factors m, builds an exponent table, and shows gcd(n, m) and lcm(n, m).

How to use in 3 steps

  1. Enter an integer n (for example, 360).
  2. Optionally enter an integer m (for example, 840).
  3. Press [Compute] to see the prime factorization, τ(n), σ(n), φ(n), the exponent table, and the factor tree.

Factor tree

For education only. The tool writes n as a product of primes and uses the exponents to compute τ(n) (number of divisors), σ(n) (sum of divisors), φ(n) (totient), and—when m is given—gcd and lcm via min/max exponents. Trial division up to 6k ± 1 remains fast for classroom-sized integers (≈10¹³).

FAQ

What integers can this tool factor?

Enter any integer with |n| ≥ 2. Very large values are supported, but the division steps may take longer to finish.

How is the factor tree drawn?

Each composite node splits by its smallest prime factor until every leaf is prime. The tree updates automatically after each calculation.

What do τ(n), σ(n), and φ(n) represent?

τ(n) is the number of positive divisors of n, σ(n) is the sum of those divisors, and φ(n) counts the integers between 1 and n that are coprime to n. This calculator derives all three directly from the exponents in the prime factorization.

Why can we get gcd and lcm from exponents?

If n and m are written as products of prime powers, then the gcd takes the minimum exponent of each prime and the lcm takes the maximum exponent. The exponent table in this calculator is a visual summary of that rule.

Related calculators