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

a315734685

代码不难, 算好久都没算出来,
如果是1-10的话, 还是可以秒出的.
x = 1
while 1:
    for i in range(1, 21):
        if x % i != 0:
            break
    else:
        print(x)   # 听说Python独有的, 循环顺利结束才会执行的语句块.
        break
    x += 1

# 大概五分钟左右跑出来的结果 232792560  

永恒的蓝色梦想

a315734685 发表于 2020-9-1 17:30
代码不难, 算好久都没算出来,
如果是1-10的话, 还是可以秒出的.
x = 1

嘿嘿，其实 else 块在 C/C++ 中是可以用 goto 实现的。

有马_冬巳

1. '''2520 是最小的能被 1-10 中每个数字整除的正整数。
   
2. 最小的能被 1-20 中每个数整除的正整数是多少？'''
   
3. 
   
4. def prime(num):
   
5.     prime_seq = [3,5]
   
6.     for factor in range(3,num):
   
7.         check_prime = 0
   
8.         if 3 > int(factor/2):
   
9.             check_prime += 1
   
10.             pass
    
11.         else:
    
12.             for prime in range(2,int(factor/2)):
    
13.                 if factor%prime == 0:
    
14.                     check_prime += 1
    
15.                     break
    
16.         if check_prime == 0:
    
17.             prime_seq.append(factor)
    
18.     global total
    
19.     total = 1
    
20.     for each in prime_seq:
    
21.         total *= each
    
22. 
    
23. def least_commonmultipler(num):
    
24.     prime(num)
    
25.     num = total
    
26.     while True:
    
27.         check = 0
    
28.         for i in range(1,21):
    
29.             if num%i != 0:
    
30.                 check += 1
    
31.                 num += total
    
32.                 break
    
33.         if check == 0:
    
34.             print(num)
    
35.             break
    
36. 
    
37. start_least_common_multipler = time.time()
    
38. least_commonmultipler(20)
    
39. time_least_common_multipler = time.time() - start_least_common_multipler
    
40. print("%f秒" %time_least_common_multipler)

复制代码

232792560
0.000496秒
改变least_commonmultipler后的参数可实现更大数字，速度奇快
原理就是吧范围内的质数找出后求积，再叠加求值

有马_冬巳

有马_冬巳 发表于 2020-10-2 16:07
232792560
0.000496秒
改变least_commonmultipler后的参数可实现更大数字，速度奇快

亲测求10万的时间是14秒

583164028

1. Range[20] // FactorInteger /@ # & // Flatten[#, 1] & //
   
2.     DeleteDuplicates // GatherBy[#, First] & // Last /@ # & //
   
3. Times @@ Apply[Power, #, {1}] &
   
4. (*代码的思路就是算出1-20所有整数分解因子，去重，排序，分组，取最大幂，构造出最终结果*)

复制代码

gonorth

适用更大的数应该。
import math as m
def is_prime(n):
    if n > 1:
        if n == 2 :
            return True
        if n % 2 == 0:
            return False
        for each in range(3, int (m.sqrt(n)+1), 2):
            if n % each == 0:
                return False
        return True
    return False

def get_prime(n):
    while 1:
        if is_prime(n):
            yield n
        n = n + 1

def solve():
    count = 2
    for i in get_prime(3):
        if i < 21:
            count *= i

        else:
            count1 = count
            print('prime', count)
            list1 = list(range(2,21))
            while 1:
                a = 1
                for x in list1:
                    if count % x != 0:
                        a = 0
                        break
                if a:
                    print(count)
                    break
                count = count + count1
            return

solve()

a1351468657

牡丹花下死做鬼 发表于 2015-7-19 21:57
不习惯用python 还是C写的没怎么优化 大概一秒不到点出的答案 232792560

牛逼！ 好想法

酷爱语言的小白

1. def numb_min(n):
   
2.     list1 = list(range(1,n+1))
   
3.     for i in range(n):
   
4.         for j  in range(i+1,n):
   
5.             if list1[j]% list1[i] == 0:
   
6.                 list1[j] = int(list1[j]/list1[i])
   
7.     m = 1
   
8.     for k in list1:
   
9.         m = m* k
   
10.     return m
    
11. print(numb_min(20))

复制代码

Kuri5u

1. #从质数往上推
   
2. num=base=19*17*11*13*2*3*5*7
   
3. lest=list(range(2,21))
   
4. flag=1
   
5. while 1:
   
6.     for each in lest:
   
7.         if num % each != 0:
   
8.             flag=0
   
9.             break
   
10.     if flag:
    
11.         print(num)
    
12.         break
    
13.     num+=base   
    

复制代码

永恒的蓝色梦想

1. from math import lcm
   
2. from functools import reduce
   
3. print(reduce(lcm, range(1, 20 + 1)))

复制代码

卢本伟牛逼

1. #include <stdio.h>
   
2. #include <math.h>
   
3. 
   
4. int count = 0;
   
5. 
   
6. int main1(void)//count = 648974546
   
7. {
   
8.         int i, result=1;
   
9.         int limit = 20, flag;
   
10.        
    
11.         //printf("上限:");
    
12.         //scanf("%d", &limit);
    
13.        
    
14.         while(1){
    
15.                 for(i=1;i<=limit;i++)
    
16.                 {
    
17.                         count += 1;
    
18.                         if(result%i != 0){
    
19.                                 result += 1;
    
20.                                 break;
    
21.                         }
    
22.                         if (i == limit){
    
23.                                 flag = 1;
    
24.                         }
    
25.                 }
    
26.                 if (result % limit == 0 && flag){
    
27.                         break;
    
28.                 }
    
29.         }
    
30.         printf("result = %d\n", result);
    
31.         printf("count = %d\n", count);
    
32.         return 0;
    
33. }
    
34. 
    
35. int is_prime(int value)
    
36. {
    
37.         int i;
    
38.         for(i=2;i<=sqrt(value);i++)
    
39.         {
    
40.                 count += 1;
    
41.                 if (i>3) i++;//step 1
    
42.                 if (value % i == 0) return 0;
    
43.         }
    
44.         return 1;
    
45. }
    
46. 
    
47. int find_step(int value)// step 2
    
48. {
    
49.         int result = 1;
    
50.         int i,j;
    
51.         for(i=2;i<=value;i++)
    
52.         {
    
53.                 count += 1;
    
54.                 if (is_prime(i)){
    
55.                         result *= i;
    
56.                 }
    
57.         }
    
58.         return result;
    
59. }
    
60. 
    
61. int is_multiply(int value, int limit)
    
62. {
    
63.         int i;
    
64.         for(i=1;i<=limit;i++)
    
65.         {
    
66.                 count += 1;
    
67.                 if (value%i!=0) return 0;
    
68.         }
    
69.         return 1;
    
70. }
    
71. 
    
72. int main(void) // count = 212
    
73. {
    
74.         int i = 1;
    
75.         int limit = 20;
    
76.         int step = find_step(limit);
    
77.        
    
78.         while(!is_multiply(step * i, limit)) i++;
    
79.         printf("result = %d\n", step * i);
    
80.         printf("count = %d\n", count);
    
81. }

复制代码

鱼塘里的鱼儿

#include <iostream>
using namespace std;
int main()
{
        for(int i=20,j=0;;i++)
        {
         for(int i0=1;i0<=20;i0++)
         {
          if(i%i0!=0)
                 break;
          if(i0==20)
                {
                 cout<<i<<endl;
                  j=1;
            }
         }
         if(j==1)
            break;
        }
                return 0;
}
//我用C++写出来的答案：232792560

ft215378

#1-20 中能被每个数整除的正整数(即最小公倍数)
'''
两个数的乘积 = 最大公约数 * 最小公倍数
'''

#求两个数最大公约数
def gcd(n1,n2):
    if n2 > 0:
        return gcd(n2, n1 % n2)
    else:
        return n1


#求两个数最小公倍数
def lcm(n1,n2):
    return n1 * n2 // gcd(n1, n2)


num = 20 #求1多少num就写多少
#将每次求得的最小公倍数作为n1再与下一个数求最小公倍数
a = lcm(1, 2)
for i in range(3, num+1):
    a = lcm(a, i)

print(a)
               
   

番杰

1. #include<stdio.h>
   
2. 
   
3. int mian(void)
   
4. {
   
5.         int flag = 0 ;
   
6.         int result ;
   
7.         for(int i = 2520 ;;i++)
   
8.         {
   
9.                 for(int j = 11;j < 21;j++)
   
10.                 {
    
11.                         if(i / j == 0)
    
12.                         {
    
13.                                 flag ++;
    
14.                         }
    
15.                         else
    
16.                                 break;
    
17.                 }
    
18.                 if(flag  == 10)
    
19.                 {
    
20.                         result = i ;
    
21.                         break;
    
22.                 }
    
23.         }
    
24.        
    
25.         printf("%d",result);
    
26.        
    
27.         return 0；
    
28. }

复制代码

learner-ray

最小能被1-20 中每个数整除的正整数是232792560

i初始

1. #include<stdio.h>
   
2. 
   
3. int main(void)
   
4. {
   
5.         int i, k, j;
   
6.         int count;
   
7.         i = k = 2*3*5*7*11*13*17*19;
   
8.        
   
9.         while (1)
   
10.         {
    
11.                 count = 0;
    
12.                 for (j = 1; j < 21; j++)
    
13.                 {
    
14.                         if (i % j == 0)
    
15.                         {
    
16.                                 count++;
    
17.                         }
    
18.                         else
    
19.                         {
    
20.                                 break;
    
21.                         }
    
22.                 }
    
23.                 if (count == 20)
    
24.                 {
    
25.                         printf("最小能被1-20 中每个数整除的正整数是%d\n", i);
    
26.                         break;
    
27.                 }
    
28.                 else
    
29.                 {
    
30.                         i = i + k;
    
31.                 }
    
32.         }
    
33.         return 0;
    
34. }

复制代码

化为2*3*5*7*11*13*17*19是抄的评论大神的，我自己写的是i初始化为21，循环i++;运行了2秒多。大神的方法只运行了0.2秒。快了十倍。

guosl

暴力但平行编程，效果也不错。

1. /*
   
2. 答案：232792560
   
3. 耗时：2.82237秒（单线程）
   
4.       0.385815秒（八线程）
   
5. */
   
6. 
   
7. #include <iostream>
   
8. #include <omp.h>
   
9. using namespace std;
   
10. 
    
11. const int nStep = 2000;
    
12. const long long INF = 0x7fffffffffffffLL;
    
13. 
    
14. inline bool chk(long long n)
    
15. {
    
16.   for (int i = 3; i < 20; ++i)
    
17.   {
    
18.     if ((n % i) != 0)
    
19.       return false;
    
20.   }
    
21.   return true;
    
22. }
    
23. 
    
24. int main(void)
    
25. {
    
26.   double t = omp_get_wtime();
    
27.   volatile long long N = 21;
    
28.   volatile bool bContinue = true;
    
29.   long long lResult = INF;
    
30. #pragma omp parallel shared(N, bContinue) reduction(min:lResult)
    
31.   while (bContinue)
    
32.   {
    
33.     long long k, lR;
    
34. #pragma omp critical
    
35.     {
    
36.       lR = lResult;
    
37.       k = N;
    
38.       N += nStep;
    
39.     }
    
40.     for (int i = k; i < k + nStep; ++i)
    
41.     {
    
42.       if (chk(i))
    
43.       {
    
44.         if (i < lR)
    
45.           lR = i;
    
46.         break;
    
47.       }
    
48.     }
    
49.     if (lR < lResult)
    
50.     {
    
51. #pragma omp critical
    
52.       {
    
53.         lResult = lR;
    
54.         bContinue = false;
    
55.       }
    
56.     }
    
57.   }
    
58.   t = omp_get_wtime() - t;
    
59.   cout << lResult << endl << t << endl;
    
60.   return 0;
    
61. }
    

复制代码

mathtimes

1. long long LGCD(long long x,long long y)
   
2. {
   
3.     if(y == 0)
   
4.         return x;
   
5.     return LGCD(y,x%y);
   
6. }
   
7. long long LLCM(long long x,long long y)
   
8. {
   
9.     return x*y/LGCD(x,y);
   
10. }
    
11. long long LCMS(long long tot,int i)
    
12. {
    
13.     if(i>1)
    
14.         return LCMS(LLCM(tot,i),i-1);
    
15.     return tot;
    
16. }
    
17. #include <stdio.h>
    
18. int main()
    
19. {
    
20.     printf("%ld",LCMS(2,20));
    
21. }

复制代码

mathtimes

1. from math import lcm
   
2. i = 1
   
3. for j in range(2,21):
   
4.     i = lcm(i,j)
   
5. print(i)

复制代码

Kazimierz

大概跑了3s 结果232792560

1. #include <stdio.h>
   
2. 
   
3. int main()
   
4. {
   
5.         int num=20,i=1;
   
6.         loop:
   
7.         {
   
8.                 num+=1;
   
9.                 for(i=1;i<=20;i++)
   
10.                 {
    
11.                         if(num%i!=0)
    
12.                         {
    
13.                                 goto loop;
    
14.                         }
    
15.                 }
    
16.         }
    
17.        
    
18.         printf("%d",num);
    
19.         return 0;
    
20. }

复制代码

jerryxjr1220

用“动态规划”的思想求解，其实很方便。
要求的数需要被1~20内所有的数整除，那么化繁为简，如果只要求这个数被1~2整除，那么这个数就是1和2的最小公倍数，1~3整除就是1~2的最小公倍数与3的最小公倍数，以此类推一直到20，所以题目就可以简化成求2个数的最小公倍数，然后循环20次就完了。
go代码：

1. package main
   
2. 
   
3. import (
   
4.         "fmt"
   
5.         "math"
   
6.         "time"
   
7. )
   
8. 
   
9. //题目5：
   
10. //
    
11. //2520 是最小的能被 1-10 中每个数字整除的正整数。
    
12. //
    
13. //最小的能被 1-20 中每个数整除的正整数是多少？
    
14. func max_elem(a, b int64) int64 {
    
15.         x := int64(math.Max(float64(a), float64(b)))
    
16.         y := int64(math.Min(float64(a), float64(b)))
    
17.         t := x % y
    
18.         for {
    
19.                 if t != 0 {
    
20.                         x = y
    
21.                         y = t
    
22.                         t = x % y
    
23.                 } else {
    
24.                         return y
    
25.                 }
    
26.         }
    
27. }
    
28. 
    
29. func min_fact(a, b int64) int64 {
    
30.         return a * b / max_elem(a, b)
    
31. }
    
32. 
    
33. func main() {
    
34.         t := time.Now()
    
35.         var i, j int64 = 2, 1
    
36.         for i = 2; i < 21; i++ {
    
37.                 j = min_fact(j, i)
    
38.         }
    
39.         fmt.Println(j)
    
40.         tt := time.Now()
    
41.         fmt.Println("耗时：", (tt.Nanosecond()-t.Nanosecond())/1e6, "ms")
    
42. }

复制代码

输出：

1. C:\Users\Anaconda\GolandProjects\EulerProject\output\go_build_Euler05_go.exe
   
2. 232792560
   
3. 耗时： 0 ms
   
4. 
   
5. 进程 已完成，退出代码为 0

复制代码

1毫秒都不用