링크
2520 is the smallest number that can be divided by each of the numbers from 1 to 10 without any remainder.
What is the smallest number that is evenly divisible by all of the numbers from 1 to 20?
We think of the sequence n_p = <n_2, n_3, n_5, n_7, n_11, ... > as a number system for positive integers. For example, the prime-exponent representation of 12 is <2, 1, 0, 0, ...> and of 18 is <1, 2, 0, 0 ...>
To multiply two numbers, we simply add their representations. In other words
k = mn iff k_p = m_p + n_p for all p
This implies that
n is divisible by m iff m_p <= n_p for all p
and it follows immediately that
k = gcd(m, n) iff k_p = min(m_p, n_p) for all p
k = lcm(m, n) iff k_p = max(m_p, n_p) for all p
Concrete Mathematics - Chapter 4.2 PRIMES
| K | N = lcm(1 ~ K) |
| 1 | 1 |
| 2 | 1 * 2 |
| 3 | 1 * 2 * 3 |
| 4 = 2 * 2 | 1 * 2 * 2 * 3 |
| 5 | 1 * 2 * 2 * 3 * 5 |
| 6 = 2 * 3 | 1 * 2 * 2 * 3 * 5 |
| 7 | 1 * 2 * 2 * 3 * 5 * 7 |
| 8 = 2 * 2 * 2 | 1 * 2 * 2 * 2 * 3 * 5 * 7 |
| 9 = 3 * 3 | 1 * 2 * 2 * 2 * 3 * 3 * 5 * 7 |
| 10 = 2 * 5 | 1 * 2 * 2 * 2 * 3 * 3 * 5 * 7 = 2520 |
| 11 | 1 * 2 * 2 * 2 * 3 * 3 * 5 * 7 * 11 |
| 12 = 2 * 2 * 4 | 1 * 2 * 2 * 2 * 3 * 3 * 5 * 7 * 11 |
| 13 | 1 * 2 * 2 * 2 * 3 * 3 * 5 * 7 * 11 * 13 |
| 14 = 2 * 7 | 1 * 2 * 2 * 2 * 3 * 3 * 5 * 7 * 11 * 13 |
| 15 = 3 * 5 | 1 * 2 * 2 * 2 * 3 * 3 * 5 * 7 * 11 * 13 |
| 16 = 2 * 2 * 2 * 2 | 1 * 2 * 2 * 2 * 2 * 3 * 3 * 5 * 7 * 11 * 13 |
| 17 | 1 * 2 * 2 * 2 * 2 * 3 * 3 * 5 * 7 * 11 * 13 * 17 |
| 18 = 2 * 3 * 3 | 1 * 2 * 2 * 2 * 2 * 3 * 3 * 5 * 7 * 11 * 13 * 17 |
| 19 | 1 * 2 * 2 * 2 * 2 * 3 * 3 * 5 * 7 * 11 * 13 * 17 |
| 20 = 2 * 2 * 5 | 1 * 2 * 2 * 2 * 2 * 3 * 3 * 5 * 7 * 11 * 13 * 17 = 232792560 |