论坛 › 【新】欧拉计划（Project Euler） › 题目5：请找出能被1~20中每个数整除的最小正整数

欧拉计划 发表于 2023-5-15 05:02:13

题目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 中每个数整除的最小正整数？


视频讲解：

https://www.bilibili.com/video/BV1no4y1g7oA/


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

**** Hidden Message *****

zhangjinxuan 发表于 2023-5-15 19:09:48

本帖最后由 zhangjinxuan 于 2023-7-4 19:35 编辑

即 lcm(1, 2, 3, 4, ... , 19, 20){:10_256:}
#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 发表于 2023-5-16 09:31:54

#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 发表于 2023-5-29 00:31:05

完成

auend 发表于 2023-6-2 14:05:14

Good object

猫熊同学 发表于 2023-6-6 09:11:13

# 方法一
# 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 发表于 2023-6-9 23:49:25

5666

LbwnbI 发表于 2023-6-11 00:06:39

6

Mr.roushan 发表于 2023-6-25 09:45:15

6

歌者文明清理员 发表于 2023-7-3 06:57:21

answer

pixie99 发表于 2023-7-7 16:34:13

。

大饼弟弟 发表于 2023-7-18 22:43:59

1

liangxixin 发表于 2023-8-1 14:23:00

1

Ian_Li 发表于 2023-8-7 19:27:25

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 发表于 2023-10-12 16:33:49

lcm()

salt_eto 发表于 2023-12-28 21:12:41

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


这代码写的和跳舞一样

salt_eto 发表于 2023-12-28 21:15:27

直接计算最大公约数
用时　<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 发表于 2024-1-4 12:21:10

test

hejiage 发表于 2024-1-4 14:59:19

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

1Asdusdhjssd 发表于 2024-2-4 16:16:30

学习了

查看完整版本: 题目5：请找出能被1~20中每个数整除的最小正整数