least common multiple algorithm

1. Method of decomposing prime factors

First write out the prime factors of these numbers. The least common multiple is equal to all their prime factors. The product of (if several prime factors are the same, compare which of the two numbers has more prime factors and multiply them more times).

For example, find the least common multiple of 45 and 30.

45=3*3*5

30=2*3*5

The different prime factors are 2, 5, and 3, which are the prime factors of both of them. Factor, since 45 has two 3s and 30 has only one 3, so when calculating the least common multiple, multiply by two 3s.

2. Formula method

Since there are two The product of numbers is equal to the product of the greatest common divisor and the least common multiple of the two numbers. That is (a, b) × [a, b] = a × b. Therefore, to find the least common multiple of two numbers, you can first find their greatest common divisor, and then use the above formula to find their least common multiple.

For example, if you find [18, 20], you get [18, 20] = 18 × 20 ÷ (18, 20) = 18 × 20 ÷ 2 = 180. To find the least common multiple of several natural numbers, you can first find the least common multiple of two of the numbers, then find the least common multiple of this least common multiple and the third number, and continue to find the last one. The least common multiple obtained in the end is the least common multiple of the numbers sought.

The above is the detailed content of least common multiple algorithm. For more information, please follow other related articles on the PHP Chinese website!