Prime Factorization, GCD and LCM Calculator

How to use

1. Type whole numbers into the box. Separate several numbers with spaces, commas or line breaks
2. With one number, its prime factorization and whether it is prime come first. Below them are the repeated division you would do by hand, a table that works out the number and sum of divisors prime by prime and multiplies them, the simplified square root, the primes before and after it, and the divisors listed in pairs that multiply to the number
3. With two or more numbers, the greatest common divisor (GCD) and least common multiple (LCM) come first. Below them are the factorizations with each prime in its own column, the simplified ratio and the common divisors. With exactly two numbers, the reduced fraction and the steps of the Euclidean algorithm, with the = signs lined up, are shown too
4. The example buttons fill in sample numbers. "Copy results" copies the results as plain text, such as 2^3 * 3^2 * 5

The results update as you type. There is no calculate button.

Example

One number (360)

360 = 2³ × 3² × 5
Not prime (composite)

Repeated division   Number and sum of divisors
2 ) 360             Prime power  Number of divisors  Sum of divisors
2 ) 180                          exponent + 1        1 + p + … + pᵉ
2 )  90             2³                    4                  15
3 )  45             3²                    3                  13
3 )  15             5                     2                   6
     5              Multiplied           24               1,170

Simplified square root  √360 = √(6² × 10) = 6√10
Neighbouring primes     359 < 360 < 367

Divisors (pairs that multiply to 360)
 1 × 360    2 × 180    3 × 120    4 × 90    5 × 72    6 × 60
 8 × 45     9 × 40    10 × 36    12 × 30   15 × 24   18 × 20

The repeated division divides by the smallest prime as many times as it goes, then by the next prime. When one prime divides five or more times in a row, only the first two rows and the last one are written, with "divide by 2 ◯ more times" in between.

Two numbers (84, 126)

GCD  42      LCM  252

         2      3      7
  84 = 2²  × 3   × 7
 126 = 2   × 3²  × 7
─────────────────────────
 GCD = 2   × 3   × 7
 LCM = 2²  × 3²  × 7

Simplified ratio  84 : 126 = 2 : 3
Reduced fraction  84/126 = 2/3 (written as stacked fractions)

Euclidean algorithm
126 = 84 × 1 + 42
 84 = 42 × 2 +  0

Three numbers (12, 18, 30)

The GCD is 6, the LCM is 180, and the ratio is 12 : 18 : 30 = 2 : 3 : 5. Neither 12 nor 18 has 5 as a prime factor, so their cells in the 5 column are empty. The GCD's 5 column is empty too, and the LCM includes 5.

How it is calculated

Prime factorization

A prime factorization writes a number as a product of primes only. The exponent is how many times the same prime is multiplied. Since 360 = 2 × 2 × 2 × 3 × 3 × 5, it is written 2³ × 3² × 5.

On paper this is found by repeated division. Divide 360 by 2 to get 180, by 2 again to get 90, and keep dividing by the smallest prime that goes, until a prime is left. The divisors down the left side, times the prime left at the bottom, are the prime factorization.

Number and sum of divisors

When n = p^a × q^b × …, the number of divisors is (a + 1) × (b + 1) × …. For 360 that is (3 + 1) × (2 + 1) × (1 + 1) = 24. The sum of divisors is (1 + p + … + p^a) × (1 + q + … + q^b) × …, which for 360 is 15 × 13 × 6 = 1170.

GCD and LCM

• GCD — the primes shared by every number, each raised to its smallest exponent, multiplied together
• LCM — every prime that appears in any number, each raised to its largest exponent, multiplied together

Writing the factorizations so that the same prime lines up in one column lets you read both off by comparing the exponents in each column. A prime missing from any number's row is left out of the GCD.

For two numbers a and b, GCD × LCM = a × b. When the GCD is 1, the numbers are called coprime.

Euclidean algorithm

Divide the larger number by the smaller one, then divide the divisor by the remainder, and repeat until the remainder is 0. The last divisor is the GCD. It finds the GCD without factoring, so it is quick even for large numbers.

Simplified square root

Primes that appear in pairs in the factorization move outside the root. Since 360 = 2² × 3² × 2 × 5, √360 = 2 × 3 × √(2 × 5) = 6√10.

FAQ

Is 1 a prime number?

No. A prime is a whole number of 2 or more whose only divisors are 1 and itself, so 1 is neither prime nor composite. For 1, the factorization is shown as 1 = 1 and its only divisor is 1.

How large can the numbers be?

Any whole number from 1 to 10^18 (1000000000000000000). For the GCD and LCM you can enter up to 20 numbers in that range. The LCM is shown in full even when it is larger than 10^18.

Why are not all divisors listed?

When there are more than 500 divisors, only 250 pairs such as "1 × 360" (500 divisors) are shown, starting from the smallest divisor, because some numbers below 10^18 have over 100,000 divisors. "Copy results" copies every divisor in ascending order.

Can I type a thousands separator, as in 1,000?

No. A comma separates numbers, so 1,000 is read as 1 and 000 (zero) and shows an error. When finding a GCD, 120,180 is read as the two numbers 120 and 180. Full-width digits and commas work.

Can I use decimals or negative numbers?

No. Prime factorization, the GCD and the LCM are calculated for whole numbers of 1 or more. 0 also shows an error.

Is the primality check reliable for large numbers?

Yes. Below 10^18 it uses a test that is certain rather than probabilistic (the Miller–Rabin test with a fixed set of 12 bases), and large prime factors are found with Pollard's rho method. Even primes close to 10^18 or products of two large primes give results right away.

Is the data I enter saved?

No. Everything is calculated in your browser, and nothing you enter is sent to a server. Reloading the page clears the input.