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

776667

def euler(x):
    result = x
    while True:
        for i in range(1,x+1):
            if result%i:
                break
        else:
            return result
        result += x

if __name__ == '__main__':
    print(euler(20))

镜中人31

s = 11* 13 * 17 * 19*2520
i = s
x = 1
while x:
    if i%s == 0:
        if i%16 == 0:
            print(i)
            x = 0
    i = i * 2

不到一秒得到答案···不过要进行相当的分析，其实分析到这个地步基本上就不需要计算机了···

jerryxjr1220

232792560
[Finished in 0.1s]

def gcd(x,y):
        maxi = 1
        for i in range(2,min(x,y)+1):
                if x%i ==0 and y%i ==0 and maxi <i:
                        maxi = i
        return maxi

def lcm(a,b):
    return a*b//gcd(a,b)
    
n = 3
m = 2
while n<=20:
    m = lcm(m,n)
    n+=1
print(m)

梦想绘制者

哎，写这个程序费了好久。
这个题目其实就是求1-20所有数的最小公倍数，将其转化为逐个求两项的最小公倍数问题。

# Python 3.5实现求解最小的能被1-20中每个数整除的正整数

def gcd(Num1,Num2):
    '''辗转相除法即欧几里德算法（Euclidean algorithm）
       用于求两个正整数之最大公因子的算法
    '''
    if Num1 < Num2:
        Num1, Num2 = Num2, Num1

    if Num1 == Num2:
        return Num2
    else:
        while True:
            r = Num1 % Num2
            if r == 0:
                return Num2
            else:
                Num1, Num2 = Num2, r


def lcm(Num1, Num2):
    '''求两个正整数之最小公倍数的算法'''
    result = Num1 * Num2 // gcd(Num1, Num2)
    return result


def smallestMultiple(start, end):
    Product = 1

    if end < start:
        start, end = end, start
    if (not isinstance(start, int)) or (not isinstance(end, int)):
          print('请输入两个正整数！')
    else:
        p = list(range(start, end + 1))        
        lenP = len(p)

        for i in range(lenP):
            n1 = Product
            n2 = p[i]
            Product = lcm(n1, n2)
                             
    return Product


sM = smallestMultiple(1, 10)
print('最小的能被1-10中每个数整除的正整数为：%d'%sM)
sM = smallestMultiple(1, 20)
print('最小的能被1-20中每个数整除的正整数为：%d'%sM)

>>>
最小的能被1-10中每个数整除的正整数为：2520
最小的能被1-20中每个数整除的正整数为：232792560

tsembrace

#找出能被1到20之间各个数整除的正整数
import math
import time

start=time.clock()
def isPrime(n):
    if n<2:
        return False
    elif n==2:
        return True
    else:
        s=int(math.sqrt(n))
        for i in range(2,s+1):
            if n%i==0:
                return False
        return True

def findMax(n):
    #找出1~n之间的各个质数，并求其乘积
    s=1
    for i in range(2,n+1):
        if isPrime(i):
            s=s*i
    lista=list(range(2,n+1))
    m=s
    #最终结果必定为前面质因数乘积的倍数
    #遍历列表，遇见不能整除的则加一次质数乘积
    #再重新遍历，直到都可以整除
    while True:
        a=1
        for x in lista:
            if m%x!=0: #不能整除，须加一次再进入到下次循环重新遍历
                a=0
                break
        if a==1:
            break
        m=m+s
    return m
 
print(findMax(20))
end=time.clock()
print("共耗时："+str(end-start)+"秒！")
    
            

toBeNot

public class SmallestMultiple 
{
        public static void main(String[] args)
        {
                //能被11-20整除的数就必然能被1-10整除，且必须是偶数
                
                int num = 0;
                int flag = 0;
                while(flag != 10)
                {        
                        flag = 0;
                        num = num + 2;
                        for(int i = 11;i <= 20;i++)
                        {
                                if(num % i == 0)
                                        flag = flag + 1;
                                else
                                        break;
                        }        
                }
                System.out.println("能被1-20整除的最小整数为：" + num);
        }
}

lyciam

折腾了好久，失败了几次，越写越复杂，再看看其他人的代码后，怎么可以这么简洁！！！还有欧几里德算法……

import math
import time
t = time.clock()

def isprime(n):
    if (n%2==0 and n!=2) or n==1: return False
    for x in range(3,int(math.sqrt(n))+1,2):
        if n%x==0 or n%5==0: return False
    else: return True

def euler05_2(count=10):
    """2520是最小能被1-10中每个数字整除的正整数，最小的能被1-20中每个数整除地正整数是多少"""
    from functools import reduce
    def findprimefactors(n): #得到一个数的质因数列表，如果 n 为质数则直接返回 [n]
        if n==1:return [1]
        if n<1:return []
        primelist = [i for i in range(2,n+1) if isprime(i)]
        iteritem = iter(primelist)
        item = next(iteritem)
        primefactors = []
        while True:
            if isprime(n) or n<3:
                primefactors.append(int(n))
                return primefactors
            elif n%item == 0:
                primefactors.append(item)
                n /= item
                continue
            try:
                item = next(iteritem)
            except:
                return primefactors
    def lcm(a,b): #得到任意两个正整数最小公倍数的质因数列表
        if type(a) is int:
            la = findprimefactors(a)
        elif type(a) is list:
            la = a
        lb = findprimefactors(b)
        temp = []
        for i in la[:]:
            if i in lb: temp.append(i); la.remove(i); lb.remove(i)
            else: temp.append(i); la.remove(i)
        if lb: temp.extend(lb)
        return temp

    # 得到从 1-count 的最小公倍数的质因数列表：
    allcm = []
    start = True
    for n in range(1,count):
        if start:
            allcm = lcm(n,n+1)
            start = False
        else:
            allcm.extend(lcm(allcm,n+1))

    # 把allcm的所有元素相乘：
    result = 1
    for n in allcm:
        result *= n   
    return result

t = time.clock()
print('answer:',euler05_2(20),'\n--time:',time.clock()-t)

写得实在是太长了点
answer:232792560
time: 0.0012959836349992165

芒果加黄桃

# encoding:utf-8
from time import time
import math
'''

2520 是最小的能被 1-10 中每个数字整除的正整数。
最小的能被 1-20 中每个数整除的正整数是多少？
'''
# 拆分素数因子
def findPrimeFactors(n, l_pr):
    if isPrime(n):
        return [n]
    sqr_n = int(math.sqrt(n)) + 1
    result = list()
    for pr in l_pr:
        if n % pr == 0:
            result.append(pr)
            result.extend(findPrimeFactors(int(n / pr),l_pr))
            break
        if pr > sqr_n:
            break
    return result

# 是否为素数
def isPrime(n):
    if not isinstance(n, int):
        print('输入有误！')
        return
    if n < 4:
        return True;
    if n % 2 == 0 or n % 3 == 0:
        return False

    for i in range(3, int(math.sqrt(n)) + 1, 2):
        if not n % i:
            return False
        
    return True
# 查找到2~N的素数    
def findPrimesToN(number):
    if number == 1:
        return [2]
    elif number == 2:
        return [2, 3]
    else:
        l_pn = [2, 3]
        n = 3
        while max(l_pn) < number:
            n += 2
            ispm = True
            sqr_n = int(math.sqrt(n))
            for t in l_pn:
                if n % t == 0:
                    ispm = False
                    break
                if t > sqr_n:
                    break
            if ispm:
                l_pn.append(n)
                
        return l_pn 


number = int(input('输入数值：'))
start = time()
result = 1
fac_dict = dict()
l_pr = findPrimesToN(int(math.sqrt(number))+1)
print(findPrimeFactors(25,l_pr))
for n in range(1, number+1):
    fac_list = findPrimeFactors(n, l_pr)
    fac_set = set(fac_list)
    for each in fac_set:
        num = fac_list.count(each)
        if not fac_dict.get(each) or fac_dict.get(each) < num:
            fac_dict[each] = num 
    #print(fac_dict)
for key in fac_dict.keys():
    result *= (key ** fac_dict.get(key))
print('能被1~~%d整除的最小整数是%d' % (number, result))
print('cost %.3f sec' % (time() - start))  

渡风

此代码使用matlab编程
Problem5所用时间为0.0016794秒
Problem5的答案为232792560

%题目5：找出最小的能被1-20中每个数整除的数 
function Output=Problem5(Input)
 tic
if nargin==0
    Input=20;
end
[Rank1,Rank2]=Com_Prime_Rank(Input);%Rank1是素数列，Rank2是合数列
L1=length(Rank1);
L2=length(Rank2);
for ii=1:L2
    for jj=1:L1
        if mod(Rank2(ii),Rank1(jj))==0
            Rank2(ii)=Rank2(ii)/Rank1(jj);
        end
    end
end
for kk=1:L2-1
    temp=kk;
    for ll=temp+1:L2
        if mod(Rank2(ll),Rank2(temp))==0
            Rank2(ll)=Rank2(ll)/Rank2(temp);
        end
    end
end
Output=prod(Rank1)*prod(Rank2);
toc
disp('此代码使用matlab编程')
disp(['Problem5所用时间为',num2str(toc),'秒'])
disp(['Problem5的答案为',num2str(Output)])
end
%% 子程序
%输入一个数使其生成小于它素数列和合数列(包括自身）
function [Output1,Output2]=Com_Prime_Rank(Input)
if nargin==0
    Input=20;
end
Rank1=2;
Rank2=0;
for ii=3:Input
     temp=ii;
     Judge=1;
     for jj=floor(sqrt(temp))+1:-1:2
         if mod(temp,jj)==0
             Judge=0;
             break
         end
     end
     if Judge==1
        Rank_Temp1=[Rank1,temp];
        Rank1=Rank_Temp1;
     else
        Rank_Temp2=[Rank2,temp];
        Rank2=Rank_Temp2;
     end
end
Output1=Rank1;
Output2=Rank2(2:end);
disp(Output2)
end

FlySelf

'''
思路:
1、找出1-20中，每个数的质因数，并存放在列表中，如果列表中的数已经包含该数的质因数，则不再向列表中添加

2、从20开始每个数验证一次，想想就感觉非常耗时，还是不去实现了
'''

import time

def is_prime(number):
    '判断是否为质数'
    flag = True
    for i in range(2, number):
        if number % i == 0:
            flag = False
    return flag

def multiple_1(number):
    '思路1完成题目'
    multiple = 1
    list_prime = [1]
    list_temp = [1]
    for i in range(1, number + 1):
        temp = i
        j = 2
        while j <= temp:
            if temp % j == 0 and is_prime(j):
                list_temp.append(j)
                temp /= j
                j = 1
            j += 1
        for n in list_temp:
            if list_temp.count(n) > list_prime.count(n):
                for m in range(0, list_temp.count(n) - list_prime.count(n)):
                    list_prime.append(n)
        list_temp.clear()
        list_temp.append(1)
    for i in list_prime:
        multiple *= i
    return multiple

start = time.clock()
print(multiple_1(20))
end = time.clock()
print('程序按思路1执行了%fs。' %(end - start))

执行结果：
232792560
程序执行了0.000230s。

夜魔时生

i=20
while True:
    for j in range(1,21):
        if i%j==0:
            continue
        else:
            break
    else:
        print(i)
        break
    i+=1
        

99592938

先把所有质数挑出来2*3*5*7*11*13*17*19，然后循环检测

num=n=2*3*5*7*11*13*17*19
f=k=1
while k:
    for i in range(1,21):
        if num%i:
            f=0
            break
    if f:
        print(num)
        k=0
    f=1
    num+=n

当然笔算也能算出结果，把剩下的合数分解因素，若能以已有质数积求得，就忽略，若不能，则再添质数，得到答案2*3*5*7*11*13*17*19*2*2*2*3=232792560

99592938

镜中人31 发表于 2016-10-6 21:07
不到一秒得到答案···不过要进行相当的分析，其实分析到这个地步基本上就不需要计算机了···

对，你再乘2就行了。
笔算也能算出结果，把质数都列出来，剩下的合数分解因素，若能以已有质数积求得，就忽略，若不能，则再添质数，最后全相乘，得到答案2*3*5*7*11*13*17*19*2*2*3*2=232792560

JonTargaryen

#include <stdio.h>

int main(void)
{
    int multiple = 0;
    int i;
    _Bool flag = 0;

    while(!flag)
    {
        multiple += 3 * 5 * 7 * 11 * 13 * 17 * 19;

        for(i = 2; i < 21; i++)
        {
            if(multiple % i)
            {
                break;
            }
        }

        if(i > 20)
        {
            break;
        }
    }

    printf("%d\n", multiple);

    return 0;
}

JonTargaryen

JonTargaryen 发表于 2017-3-27 10:42

def main():
    result = 0

    while True:
        result += 2 * 3 * 5 * 7 * 11 * 13 * 17 * 19
        for each in range(1, 21):
            if result % each:
                break

        if each == 20:
            break

    print(result)

if __name__ == "__main__":
    main()

Eagle.Tong

#求能被1-20中每个数整除的最小正整数
#设a,b的最大公约数为(a,b),最大公倍数为[a,b]
#则有 a*b = (a,b)*[a,b]

import time


start = time.time()
def gcd(x,y):
    x,y = max(x,y),min(x,y)
    r = x%y
    if r == 0:
        return y
    else:
        return gcd(y,r)


n1 = 2*3//gcd(2,3)

for n2 in range(4,21):
    n1 = n1*n2//gcd(n1,n2)

print(n1)

end = time.time()

print(end-start)

结果：232792560
时间：0.0070035457611083984s

天之南

#include<stdio.h>

int main()
{
        const int L = 20;
        int num = 1;
        int * arr = malloc(L * sizeof(int));
        for (int i = 0;i < L;i++)
        {
                arr[i] = i + 1;
                for (int j = 0;j < i;j++)
                {
                        if (arr[i] % arr[j] == 0)
                        {
                                arr[i] /= arr[j];
                        }
                }
                num *= arr[i];
        }
        printf("%d\n", num);
        free(arr);
        return 0;
}

铭记太阳

答案是232792560

#include<stdio.h> 
//20以内涉嫌重复的只有2,3,5,7,将其除掉即可 
//2最多有5次：16，3最多有2次：9 
int main(void)
{
        int i,num,rst=1; 
        
        for(i=2;i<=20;++i)
        {
                num = i;
                if(num%2==0)
                        while(num%2==0)        num /= 2;
                if(num%3==0)
                        while(num%3==0)        num /= 3;
                if(num%5==0)
                        num /= 5;
                if(num%7==0)
                        num /= 7;
                rst = rst * num; 
        }
        
        rst = rst * 16 * 9 * 5 * 7;
        //乘2^4=16,3^2=9,5,7 
        printf("%d\n",rst);
        return 0;
}

soby1984

#include<stdio.h>
int main()
{
        int x[21]={0};
        int a,b;
        
        for(a=20;x[20]==0;a++)
        {
        
                for(b=1;b<21;b++)
                {
                        if(a%b==0)
                        {
                                
                                x[b]=a;
                        }
                        else
                        {
                                
                                break;
                        }        
                        
                }
        
        }
        
        printf("%d ",x[20]);

        return 0;
}

求告知这种算法怎么修改能更快速和简单

格式化、

public static void main(String[] args) {
//                5、2520是最小能被1-10每个数字整除的正整数。最小的能被1-20中每个数整除的正整数是多少？
                int i=20;
                while(!cmp(i)){
                        i++;
                }
                System.out.println(i);
        }
        public static boolean cmp(int num) {
                for(int i=2;i<21;i++){
                        if(num%i!=0){
                                return false;
                        }
                }
                return true;
        }

感觉速度有点慢