c++ - 我如何找到可以除以所有数字的最小数字 1 :n with no remainder?

Question

我一直在尝试解决 Project Euler 上的第 5 个问题

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?

我决定更进一步，我决定让它找到能被从 1 到 limit 的所有数字整除的最小正数，其中 limit 是用户定义的。

当我执行我的程序时，问题开始了，它立即打印出 0。我尝试跟踪我的代码，但没有成功。

#include <iostream>
using std::cout;
using std::cin;

bool isRemainderFree(int num, int limit){
    bool bIsRemainderFree = true;
    if(num < limit){
        bIsRemainderFree = false;
    }else{
        for(int i=1; i <= limit; i++){
        if(num % i != 0){
            bIsRemainderFree = false;
            break;
        }
      }
    }
    return bIsRemainderFree;
}

int smallestMultiple(int limit){
    int smallestNum = 10;
    for(int i=1; i <= limit; i++){
        bool bFree = isRemainderFree(i, 10);
        if(bFree){
            cout << i << " is divisible by all numbers from 1 to " << limit << ".\n";
            smallestNum = i;
            return smallestNum;
            break;
        }
    }

}

int main(){
    int limit;
    cin >> limit;
    int smallestNum = smallestMultiple(limit);
    cout << smallestNum;
    return 0;
}

Answer 1

答案应该是所有数字的最小最小公倍数，可以通过以下方式轻松完成

int gcd(int a, int b){
    if(b==0)
        return a;
    return gcd(b, a%b);
}
int main() {
    int limit = 10, lcm = 1;
    for(int i=1; i<=limit; i++){
        lcm = (lcm * i)/gcd(lcm,i);
    }
    printf("%d\n", lcm); // prints 2520
    return 0;
}