题目5：请找出能被1~20中每个数整除的最小正整数

欧拉计划

题目5：请找出能被1~20中每个数整除的最小正整数

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?

题目翻译：

2520 是能被 1~10 中每个数字整除的最小正整数。

请找出能被 1~20 中每个数整除的最小正整数？


视频讲解：




思路解析及源码参考（C & Python）：

游客，如果您要查看本帖隐藏内容请回复

zhangjinxuan

即 lcm(1, 2, 3, 4, ... , 19, 20)

#include <bits/stdc++.h>
using namespace std;


int main() {
        int ans = 1;
        for (int i = 1; i <= 20; ++i) {
                int tmp = __gcd(ans, i);
                ans = 1ll * ans * i / tmp;
        }
        printf("%d\n", ans);
        return 0;
}

Kazimierz

#include <bits/stdc++.h>
using namespace std;

typedef long long LL;

LL gcd(LL a,LL b)
{
    return b?gcd(b,a%b):a;
}

LL lcm(LL a,LL b)
{
    return a*b/gcd(a,b);
}

int main()
{
    LL ans = 1;
    for(int i=1;i<=20;i++) ans = lcm(ans,i);
    cout<<ans<<endl;
    return 0;
}

a8634944

完成

auend

Good object

猫熊同学

# 方法一
# 232792560
# 一共用时14.778秒

i = 21
while True:
    if i % 6 == 0:
        if i % 7 == 0:
            if i % 8 == 0:
                if i % 9 == 0:
                    if i % 10 == 0:
                        if i % 11 == 0:
                            if i % 12 == 0:
                                if i % 13 == 0:
                                    if i % 14 == 0:
                                        if i % 15 == 0:
                                            if i % 16 == 0:
                                                if i % 17 == 0:
                                                    if i % 18 == 0:
                                                        if i % 19 == 0:
                                                            if i % 20 == 0:
                                                                print(i)
                                                                break
                                                            else:
                                                                i += 1
                                                        else:
                                                            i += 1
                                                    else:
                                                        i += 1
                                                else:
                                                    i += 1
                                            else:
                                                i += 1
                                        else:
                                            i += 1
                                    else:
                                        i += 1
                                else:
                                    i += 1
                            else:
                                i += 1
                        else:
                            i += 1
                    else:
                        i += 1
                else:
                    i += 1
            else:
                i += 1
        else:
            i += 1
    else:
        i += 1

# 方法二
# 232792560
# 一共用时57.203秒

is_true = 0
if_false = 0

i = 21
while True:
    for j in range(6, 21):
        if i % j == 0:
            is_true = 1
            is_false = 0
        else:
            is_false = 1
            is_true = 0
        if is_false == 1:
            break
    if is_true == 1:
        print(i)
        break
    i += 1

hszenoa

5666

LbwnbI

6

Mr.roushan

6

歌者文明清理员

answer

pixie99

。

大饼弟弟

1

liangxixin

1

Ian_Li

public static void main(String[] args) {
        long res = 1;
        for (long i = 2; i < 21; i++) {
            res = lcm(res, i);
        }
        System.out.println(res);
    }

    private static long lcm(long a, long b) {
        return a * b / gcd(a, b);
    }

    private static long gcd(long a, long b) {
        if (b == 0) return a;
        return gcd(b,a % b);
    }

chenxyong

lcm()

salt_eto

猫熊同学 发表于 2023-6-6 09:11
# 方法一
# 232792560
# 一共用时14.778秒

这代码写的和跳舞一样

salt_eto

直接计算最大公约数
用时　<0.01ms

int main ( )
{
    Ulong res = 1;
    for (int i = 1; i <= 20; i++)
    {
        res = res * i / std::gcd (res, i);
    }
    cout<<ans<<endl;
}

1433391058

test

hejiage

一路看过来，还是鱼c做得最好

1Asdusdhjssd

学习了