【歐拉計劃第 5 題】最小公倍數 Smallest multiple

Problem 5 Smallest multiple

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 positive number that is evenly divisible by all of the numbers from 1 to 20?

問題 5 最小公倍數

2520 是可以除以 1 到 10 的每個數字而沒有任何餘數的最小數字。

能被 1 到 20 的所有數整除的最小正數是多少？

理論要點

最小公倍數

引用下百科的解釋：

兩個或多個整數公有的倍數叫做它們的公倍數，其中除 0 以外最小的一個公倍數就叫做這幾個整數的最小公倍數

整數 的最小公倍數記為 ，同樣的， 的最小公倍數記為

那如何計算最小公倍數呢?

首先，把這幾個數的質因數寫出來，最小公倍數等于它們所有的質因數的乘積（如果有幾個質因數相同，則比較兩數中哪個數有該質因數的個數較多，乘較多的次數）

例如：

最大公約數

最大公約數， 的最大公約數記為

即：短除尋找公因數數，直到找不出公因數，左側公因數乘積即為最大公約數

最大公約數和最小公倍數的關系

兩個數的乘積等于這兩個數的最大公約數與最小公倍數的乘積

若有兩數 ，它們的最大公約數是 ，最小公倍數是

那麼

該公式可改寫為

那麼，我們給出最小公倍數的計算公式

歐幾裡得算法

又稱輾轉相除法，用于計算兩個非負整數

• 用較小數除較大數
• 再餘數（第一餘數）去除除數
• 再用出現的餘數（第二餘數）去除第一餘數
• 疊代，直到最後餘數是0為止。若要求兩個數的最大公約數，則最後的除數就是這兩個數的最大公約數

計算公式

思路分析

代碼實作

/*
 * @Author: coder-jason
 * @Date: 2022-04-11 14:08:31
 * @LastEditTime: 2022-04-11 14:59:47
 */
#include <iostream>
using namespace std;

typedef long long variable; // 定義類型别名

variable gcd(variable a, variable b) // gcd 實作
{
    return b>0 ? gcd(b, a % b) : a;
}

int main()
{
    variable ans = 1;
    for (int i = 2; i <= 20; i++)
    {
        ans = ans * i / gcd(ans, i);
    }
    cout << ans << endl;
    return 0;
}