zl程序教程

您现在的位置是:首页 >  其他

当前栏目

Smallest multiple

2023-03-14 10:17:14 时间
#include<iostream>
#include<algorithm>
using namespace std;
int lcm(int a ,int b)
{
    int big=max(a,b);
    int small=min(a,b);
    int max=a*b;
    for(int i=big; i<max; i+=big)
    {
        if(i%small==0)
            return i;
    }
    return max;
}
int main()
{
    int sum,a=1,b=2;
    while(b!=20)
    {
       sum=lcm(a,b);
       a=sum;
       b++;
    }
    cout<<sum<<endl;
    return 0;
}

  https://projecteuler.net/problem=5

求1-20的最小公倍数。

求两个数a,b的最小公倍数嘛,先取出其中较大的那个比如a,然后再用k*a去试探能否被较小那个数整除,其中,k是从1开始的自然数 k*a<a*b。

另外一种比较好的方法,以n取10为例

2,3,4,5,6,7,8,9,10 (1没有什么意义,忽略掉了)

将这些数字分解质因数:

2, 3, 2*2, 5, 2*3, 7, 2*2*2, 3*3, 2*5

这些质数分别是2, 3, 5, 7

最终答案可以表示为:

2^a * 3^b * 5^c * 7^d (其中,x^y表示x的y次方)

其中的英文字母表示在上面分解质因数时所得到的表达式中质因数在同一个表达式中出现的次数的最大值。

质因数2出现次数最多是在8=2*2*2中,其出现了3次,所以a为3。

同理可得到:2^3 * 3^2 * 5^1 * 7^1 = 2520。