题目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 中每个数整除的正整数是多少？

翅膀团

#include <stdio.h>

int main(void)
{
    int i,j;
    i = 20;
    while(1)
    {
        i++;
        for(j=1;j<=20;j++)
        {
            if(i % j != 0)
            {
                goto z;
            }
        }
        printf("%d\n",i);
        return 0;
z:       j=1;
    }
   
}

如果有错误希望指出

无名侠

翅膀团 发表于 2015-7-3 16:16
#include

void main()

执行结果是对的，但是有语法错误。
你的main函数返回值类型是void
你在代码里用了return 0

无名侠

好了，老师。 代码写的有些冗杂。
fun(10) = 2520
fun(20) 程序还在跑。  
老师能看看我这是哪里出问题了？
@小甲鱼 help
@～风介～ help

1. def fun(x):
   
2.         i = 1
   
3.         flag = True
   
4.         while flag:
   
5.                 for j in range(1,x+1):
   
6.                         if i%j!=0:
   
7.                                 flag = False
   
8.                                 break
   
9.                 if flag:
   
10.                         print(i)
    
11.                         return
    
12.                 i+=1
    
13.                 flag = True
    

复制代码

翅膀团

无名侠 发表于 2015-7-10 08:02
执行结果是对的，但是有语法错误。
你的main函数返回值类型是void
你在代码里用了return 0

习惯用void main了，忘记改int main了

牡丹花下死做鬼

无名侠 发表于 2015-7-10 08:17
好了，老师。 代码写的有些冗杂。
fun(10) = 2520
fun(20) 程序还在跑。  

不习惯用python 还是C写的没怎么优化 大概一秒不到点出的答案 232792560

1. #define COUNT 20
   
2. #include <stdio.h>
   
3. #include <string.h>
   
4. int f(int a,int b)
   
5. {
   
6.         int t;
   
7.         if(a>b)
   
8.         {
   
9.                 t=a;a=b;b=t;
   
10.         }
    
11.         for(t=a;t%a||t%b;t+=a){}; /*求最小公倍数辗除法的缩写看不懂可以写辗除法完整的样子*/
    
12.         return t;
    
13. }
    
14. int main()
    
15. {
    
16.         int a[COUNT];
    
17.         int i,k;
    
18.         for(i=0;i<COUNT;i++)
    
19.         {
    
20.                 a[i]=i+1; /*给数组赋值1，2，3，......20*/
    
21.         }
    
22.         k=1;
    
23.         for(i=0;i<COUNT;i++)
    
24.         {
    
25.         k=f(k,a[i]); /*计算1 2 的公倍数，在求 这个公倍数 和3 的公倍数然后这个公倍数再和4求公倍数
    
26.         一直求到20*/
    
27.         }
    
28.         printf("\n最小公倍数为:%d\n",k);
    
29.         return 0;
    
30. }

复制代码

maoguy

1. #include <iostream>
   
2. using namespace std;
   
3. 
   
4. int main ()
   
5. {
   
6.         int i,j,flag;
   
7. 
   
8.         for (i = 20 ; ; i ++)
   
9.         {
   
10.                 for (j = 11 ; j <= 20 ; j ++)
    
11.                 {
    
12.                         if (i % j != 0)
    
13.                         {
    
14.                                 flag = 0;
    
15.                                 break;
    
16.                         }
    
17.                         else if (i % j == 0)
    
18.                         {
    
19.                                 flag = 1;
    
20.                                 continue;
    
21.                         }
    
22.                 }
    
23. 
    
24.                 if (flag == 1)
    
25.                 {
    
26.                         cout<<"最小的能被1-20每个数整除的数为："<<i<<endl;
    
27.                         break;
    
28.                 }
    
29.                 else
    
30.                         continue;
    
31.         }
    
32. 
    
33.         return 0;
    
34. 
    
35. }

复制代码

输出结果：
最小的能被1-20每个数整除的数为：232792560

飘飞的白杨

1. import math
   
2. def lcm(a,b):
   
3.         return a*b//math.gcd(a,b)
   
4. 
   
5. n = 3
   
6. m = lcm(n-1,n)
   
7. while n<=20:
   
8.         m = lcm(m,n+1)
   
9.         n+=1
   
10. print(m)

复制代码

huomqh

1. list1=list(range(2,21))
   
2. i=j=2*3*5*7*11*13*17*19
   
3. 
   
4. while 1:
   
5.     a=1
   
6.     print(i)
   
7.     for x in list1:
   
8.         
   
9.         if i%x !=0:
   
10.             a=0
    
11.             #print(i,x,end="")
    
12.             #print('no!')
    
13.             break
    
14.     if a:
    
15.         print(i)
    
16.         break
    
17.     i+=j
    
18.         
    

复制代码

答案232792560

冷钟天

1. for i in range(380,x,380):
   
2.         a=0
   
3.         for j in range(1,21):
   
4.                 if i%j==0:
   
5.                         a+=1
   
6.         if a==20:
   
7.                 print('最小的数是',i)
   
8.                 break

复制代码

冷钟天

huomqh 发表于 2016-6-13 14:28
答案232792560

i=j=2*3*5*7*11*13*17*19
这是什么原理？

huomqh

冷钟天 发表于 2016-7-4 19:52
i=j=2*3*5*7*11*13*17*19
这是什么原理？

20以内的质数，相乘保证了这个数能被所有质数整除，然后在往上翻倍就好了啊。

huomqh

冷钟天 发表于 2016-7-4 19:43

range(380,x,380):
是啥？

冷钟天

huomqh 发表于 2016-7-4 22:35
20以内的质数，相乘保证了这个数能被所有质数整除，然后在往上翻倍就好了啊。

这个原理好给力。学习了

冷钟天

huomqh 发表于 2016-7-4 22:40
range(380,x,380):
是啥？

20跟19的乘积。。。。只是缩短一下迭代。不过跟你那方法比起来貌似没办法比

幻世伽蓝

1. a = 1
   
2. for x in range(1, 21):
   
3.     a *= x
   
4. print(' = ' ,a)
   
5. 
   
6. def p(num):
   
7.     for i in range(1, 21):
   
8.         if num % i == 0:
   
9.             continue
   
10.         else:
    
11.             return 0
    
12.     return num
    
13. 
    
14. for each in range(1, a +1):
    
15.     if p(each):
    
16.         print(each)
    
17.         break
    

复制代码

虽然能出结果，但用了4分多钟，可怕，有没有简单点的

huomqh

幻世伽蓝 发表于 2016-7-6 15:13
虽然能出结果，但用了4分多钟，可怕，有没有简单点的

看我那个方法，用时：0.0156 s

始终

1. import math
   
2. 
   
3. def deal(n):
   
4.     lst = list(range(2, n + 1))
   
5.     l = len(lst)
   
6.     i = 0
   
7.     while i < l:
   
8.         j = i + 1
   
9.         while j < l:
   
10.             if lst[j] % lst[i] == 0:
    
11.                 lst[j] = int(lst[j] / lst[i])
    
12.             j += 1
    
13.         i += 1
    
14.     return lst
    
15. 
    
16. def product(lst):
    
17.     p = 1
    
18.     for i in lst:
    
19.         p *= i
    
20.     return p
    
21. print(product(deal(20)))
    

复制代码

232792560

impossible

1. #include <iostream>
   
2. #include <cmath>
   
3. #include <vector>
   
4. 
   
5. inline unsigned is_prime(unsigned a);
   
6. 
   
7. int main()
   
8. {
   
9.         std::vector<unsigned int>v={20,18,15,14,12,10,8,6,16,9,5,7,11,13,17,19};
   
10.         unsigned int result=1;
    
11.        
    
12.         for(int i=0;i<8;i++){
    
13.                 if(is_prime(v[i]))v[i]=1;
    
14.         }
    
15.         for(auto &v2:v)
    
16.                 result*=v2;
    
17.        
    
18.         std::cout<<result<<std::endl<<std::endl;
    
19.        
    
20.         return 0;
    
21. }
    
22. inline unsigned is_prime(unsigned a)
    
23. {
    
24.         unsigned describe=0,i=2;
    
25.        
    
26.         for(;i<sqrt(a);i++){
    
27.                 if(a%i==0){
    
28.                         describe=1;
    
29.                         break;
    
30.                 }
    
31.         }
    
32.        
    
33.         return describe;
    
34. }

复制代码

Plusenxue

1. def gcd(x,y):
   
2.     if x == 0:
   
3.         return y
   
4.     else:
   
5.         if x < y:
   
6.             x,y = y,x
   
7.         x = x%y
   
8.         return gcd(x,y)
   
9. 
   
10. def lcd(x,y):
    
11.     return x*y//gcd(x,y)
    
12. 
    
13. n = 1
    
14. for i in range(1,20):
    
15.     n = lcd(n,i)
    
16. 
    
17. print(n)
    

复制代码