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

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[COUNT];
        int i,k;
        for(i=0;i<COUNT;i++)
        {
                a[i]=i+1; /*给数组赋值1，2，3，......20*/
        }
        k=1;
        for(i=0;i<COUNT;i++)
        {
        k=f(k,a[i]); /*计算1 2 的公倍数，在求 这个公倍数 和3 的公倍数然后这个公倍数再和4求公倍数
        一直求到20*/
        }
        printf("\n最小公倍数为:%d\n",k);
        return 0;
}

maoguy

#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

飘飞的白杨

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)

huomqh

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
这是什么原理？

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的乘积。。。。只是缩短一下迭代。不过跟你那方法比起来貌似没办法比

幻世伽蓝

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

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

huomqh

幻世伽蓝 发表于 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[j] % lst[i] == 0:
                lst[j] = int(lst[j] / lst[i])
            j += 1
        i += 1
    return lst

def product(lst):
    p = 1
    for i in lst:
        p *= i
    return p
print(product(deal(20)))

232792560

impossible

#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[i]))v[i]=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;
}

Plusenxue

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)