题目5：找出最小的能被1-20中每个数整除的数
本帖最后由 欧拉计划 于 2017-1-14 17:44 编辑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 中每个数整除的正整数是多少？
本帖最后由 翅膀团 于 2015-11-16 14:09 编辑
#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) 程序还在跑。
老师能看看我这是哪里出问题了？{:5_92:}
@小甲鱼 help
@～风介～ help
def fun(x):
i = 1
flag = True
while flag:
for j in range(1,x+1):
if i%j!=0:
flag = False
break
if flag:
print(i)
return
i+=1
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
#define COUNT 20
#include <stdio.h>
#include <string.h>
int f(int a,int b)
{
int t;
if(a>b)
{
t=a;a=b;b=t;
}
for(t=a;t%a||t%b;t+=a){}; /*求最小公倍数辗除法的缩写看不懂可以写辗除法完整的样子*/
return t;
}
int main()
{
int a;
int i,k;
for(i=0;i<COUNT;i++)
{
a=i+1; /*给数组赋值1，2，3，......20*/
}
k=1;
for(i=0;i<COUNT;i++)
{
k=f(k,a); /*计算1 2 的公倍数，在求 这个公倍数 和3 的公倍数然后这个公倍数再和4求公倍数
一直求到20*/
}
printf("\n最小公倍数为:%d\n",k);
return 0;
} #include <iostream>
using namespace std;
int main ()
{
int i,j,flag;
for (i = 20 ; ; i ++)
{
for (j = 11 ; j <= 20 ; j ++)
{
if (i % j != 0)
{
flag = 0;
break;
}
else if (i % j == 0)
{
flag = 1;
continue;
}
}
if (flag == 1)
{
cout<<"最小的能被1-20每个数整除的数为："<<i<<endl;
break;
}
else
continue;
}
return 0;
}
输出结果：
最小的能被1-20每个数整除的数为：232792560
本帖最后由 飘飞的白杨 于 2016-6-10 22:25 编辑
import math
def lcm(a,b):
return a*b//math.gcd(a,b)
n = 3
m = lcm(n-1,n)
while n<=20:
m = lcm(m,n+1)
n+=1
print(m) list1=list(range(2,21))
i=j=2*3*5*7*11*13*17*19
while 1:
a=1
print(i)
for x in list1:
if i%x !=0:
a=0
#print(i,x,end="")
#print('no!')
break
if a:
print(i)
break
i+=j
答案232792560 for i in range(380,x,380):
a=0
for j in range(1,21):
if i%j==0:
a+=1
if a==20:
print('最小的数是',i)
break
huomqh 发表于 2016-6-13 14:28
答案232792560
i=j=2*3*5*7*11*13*17*19
这是什么原理？
冷钟天 发表于 2016-7-4 19:52
i=j=2*3*5*7*11*13*17*19
这是什么原理？
20以内的质数，相乘保证了这个数能被所有质数整除，然后在往上翻倍就好了啊。 冷钟天 发表于 2016-7-4 19:43
range(380,x,380):
是啥？ huomqh 发表于 2016-7-4 22:35
20以内的质数，相乘保证了这个数能被所有质数整除，然后在往上翻倍就好了啊。
{:5_100:}这个原理好给力。学习了 huomqh 发表于 2016-7-4 22:40
range(380,x,380):
是啥？
20跟19的乘积。。。。只是缩短一下迭代。不过跟你那方法比起来貌似没办法比 a = 1
for x in range(1, 21):
a *= x
print(' = ' ,a)
def p(num):
for i in range(1, 21):
if num % i == 0:
continue
else:
return 0
return num
for each in range(1, a +1):
if p(each):
print(each)
break
虽然能出结果，但用了4分多钟，可怕，有没有简单点的{:5_111:} 幻世伽蓝 发表于 2016-7-6 15:13
虽然能出结果，但用了4分多钟，可怕，有没有简单点的
看我那个方法，用时：0.0156 s import math
def deal(n):
lst = list(range(2, n + 1))
l = len(lst)
i = 0
while i < l:
j = i + 1
while j < l:
if lst % lst == 0:
lst = int(lst / lst)
j += 1
i += 1
return lst
def product(lst):
p = 1
for i in lst:
p *= i
return p
print(product(deal(20)))
232792560 #include <iostream>
#include <cmath>
#include <vector>
inline unsigned is_prime(unsigned a);
int main()
{
std::vector<unsigned int>v={20,18,15,14,12,10,8,6,16,9,5,7,11,13,17,19};
unsigned int result=1;
for(int i=0;i<8;i++){
if(is_prime(v))v=1;
}
for(auto &v2:v)
result*=v2;
std::cout<<result<<std::endl<<std::endl;
return 0;
}
inline unsigned is_prime(unsigned a)
{
unsigned describe=0,i=2;
for(;i<sqrt(a);i++){
if(a%i==0){
describe=1;
break;
}
}
return describe;
} def gcd(x,y):
if x == 0:
return y
else:
if x < y:
x,y = y,x
x = x%y
return gcd(x,y)
def lcd(x,y):
return x*y//gcd(x,y)
n = 1
for i in range(1,20):
n = lcd(n,i)
print(n)