题目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)

1. #include <bits/stdc++.h>
   
2. using namespace std;
   
3. 
   
4. 
   
5. int main() {
   
6.         int ans = 1;
   
7.         for (int i = 1; i <= 20; ++i) {
   
8.                 int tmp = __gcd(ans, i);
   
9.                 ans = 1ll * ans * i / tmp;
   
10.         }
    
11.         printf("%d\n", ans);
    
12.         return 0;
    
13. }

复制代码

Kazimierz

1. #include <bits/stdc++.h>
   
2. using namespace std;
   
3. 
   
4. typedef long long LL;
   
5. 
   
6. LL gcd(LL a,LL b)
   
7. {
   
8.     return b?gcd(b,a%b):a;
   
9. }
   
10. 
    
11. LL lcm(LL a,LL b)
    
12. {
    
13.     return a*b/gcd(a,b);
    
14. }
    
15. 
    
16. int main()
    
17. {
    
18.     LL ans = 1;
    
19.     for(int i=1;i<=20;i++) ans = lcm(ans,i);
    
20.     cout<<ans<<endl;
    
21.     return 0;
    
22. }

复制代码

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

1. public static void main(String[] args) {
   
2.         long res = 1;
   
3.         for (long i = 2; i < 21; i++) {
   
4.             res = lcm(res, i);
   
5.         }
   
6.         System.out.println(res);
   
7.     }
   
8. 
   
9.     private static long lcm(long a, long b) {
   
10.         return a * b / gcd(a, b);
    
11.     }
    
12. 
    
13.     private static long gcd(long a, long b) {
    
14.         if (b == 0) return a;
    
15.         return gcd(b,a % b);
    
16.     }

复制代码

chenxyong

lcm()

salt_eto

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

这代码写的和跳舞一样

salt_eto

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

1. int main ( )
   
2. {
   
3.     Ulong res = 1;
   
4.     for (int i = 1; i <= 20; i++)
   
5.     {
   
6.         res = res * i / std::gcd (res, i);
   
7.     }
   
8.     cout<<ans<<endl;
   
9. }

复制代码

1433391058

test

hejiage

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

1Asdusdhjssd

学习了