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

运维小书童

1. #最小的能倍1-20 中每个数整除的正整数
   
2. #所求的数是1-20 中质数列表乘积的倍数
   
3. import time
   
4. start = time.clock()
   
5. 
   
6. def prime(param):
   
7.     '获得小于指定整数的质数列表'
   
8.     list = []
   
9.     for i in range(1,param+1):
   
10.         count = 0
    
11.         for j in range(2,i):
    
12.             if i%j == 0:
    
13.                 count += 1
    
14.             if count > 1:
    
15.                 break
    
16.         if count == 0:
    
17.             list.append(i)
    
18.     return(list)
    
19. 
    
20. def SmallestMutiple(number):
    
21.     '计算能被1-number中每个数整除的最小正整数，所求的数是1-number 中质数列表乘积的倍数'
    
22.     numplus = 1
    
23.     for each in prime(number):
    
24.         numplus *= each
    
25.     num = numplus
    
26.     while 1:
    
27.         temp = 0
    
28.         for each in range(1,number+1):
    
29.             if num%each !=0 :
    
30.                 temp = 1
    
31.                 break
    
32.         if temp == 0:
    
33.             return num
    
34.         else:
    
35.             num += numplus
    
36. 
    
37. print(SmallestMutiple(20))
    
38. end = time.clock()
    
39. print('耗时%f s'%(end - start))

复制代码

麦特的灰

1. #找出最小的能被1-20中每个数整除的正整数
   
2. num = 2*3*5*7*11*13*17*19
   
3. numx=4*6*8*9*10*12*14*15*16*18*20
   
4. for i in range (1,numx):
   
5.     nums=i*num
   
6.     if (nums%14==0 and nums%16==0 and nums%18==0 and nums%20==0):
   
7.         print (i)
   
8.         print (nums)
   
9.         break

复制代码

BngThea

1. orig = 1
   
2. for i in range(2,21):
   
3.     orig *= i
   
4. 
   
5.    
   
6. def check(num):
   
7.     for each in range(2,21):
   
8.         if not (num % each):
   
9.             return False
   
10.     return True
    
11. 
    
12. list1 = [2,3,5,7]
    
13. 
    
14. flage = True
    
15. while flage:
    
16.     result = orig
    
17.     for each in list1:
    
18.         orig //= each
    
19.         if not check(orig):
    
20.             orig *= each
    
21.             if result == orig:
    
22.                 flage = False
    
23.             break
    
24.         
    
25. print(result)

复制代码

wuxianke

print('What is the smallest positive number that is evenly divisible by all \
of the numbers from 1 to 20')
print('--------------------------------------------------------------------')
import math
import time

def IsPrime(n):     #判断是否为质数的函数
    Nsqrt = math.ceil(n ** 0.5)
    Jug = 0
    for i in range(2,Nsqrt+1):
        if n % i == 0:
            Jug = 0
            break
        else:
            Jug = 1
    if (n == 2) or (n == 1):
        Jug = 1
    return Jug

def Facting(n):
    FacList = []        #将分解出来的质数放入该列表
    if IsPrime(n) == 1:
        FacList = [n]
    else:
        for i in range(2,math.ceil(n/2)+1):
            if n % i != 0:
                continue
            else:
                while (n % i == 0):
                    FacList.append(i)
                    n = n/i
    return FacList        

def FindSmall(Nums=[]):
    start = time.clock()
    NumCList = []
    EvenNum = []
    PrimeNum = []
    NumFact = []        #用于存储分解质因数
    NumC = 0        #用于统计最多出现次数
    Smallsum = 1
    for i in Nums:
        if IsPrime(i) == 1:
            PrimeNum.append(i)
        else:
            EvenNum.append(i)
    for j in PrimeNum:      #循环目的：找出每个质数出现的最大次数
        NumC = 0   
        for k in Nums:      #循环目的：找出同一个质数出现的最大次数
            NumFact = Facting(k)
            A = NumFact.count(j)
            if A >= NumC:
                NumC = A
        NumCList.append(NumC)       #将最大次数写进列表，并且，是与质数表一一对应
    print(PrimeNum)
    print(NumCList)
    t = 0
    while t < len(PrimeNum)-1:
        t += 1
        Smallsum = Smallsum * (int(PrimeNum[t]) ** int(NumCList[t]))
              
    print(Smallsum)
    end = time.clock()
    print("运行时间:%fs" %(end - start))



该数组所有的质数是: [1, 2, 3, 5, 7, 11, 13, 17, 19]
每个质数对应的次幂: [1, 4, 2, 1, 1, 1, 1, 1, 1]
232792560
运行时间:0.001115s

jerryxjr1220

AArdio编译：

1. import console;
   
2. import time.timer
   
3. 
   
4. console.setTitle("test");
   
5. 
   
6. time.timer.start();
   
7. 
   
8. var gcd = function(a,b){
   
9.         while a {
   
10.                 a, b = b%a, a
    
11.         }
    
12.         return b
    
13. }
    
14. 
    
15. t = 1
    
16. for i=2;20;1 {
    
17.         t *= i/gcd(t,i);
    
18. }
    
19. console.print(t);
    
20. console.print(time.timer.endTick(), '毫秒');
    
21. console.pause();
    
22. console.close()

复制代码

232792560
0.24593371152878        毫秒
请按任意键继续 ...

zjhnz

答案 232792560 用时 0.6814

#include <stdio.h>

int isdiv(int n)
{
        for (int i=1; i<=20; i++)
        {
                if(n%i!=0)
                {
                        return 0;
                }
        }
        return 1;
}

int main(void)
{
        unsigned long long n=1;
        for(int j=1; j<=20; j++)
        {
                n=n*j;
               
        }
        printf("%lld",n);
        for(int i=20; i<n; i=i+20)
        {
                if(isdiv(i))
                {
                        printf("\n%d",i);
                        break;
                }
        }
}

幻世伽蓝

1. #include <stdio.h>
   
2. #include <stdlib.h>
   
3. 
   
4. int main()
   
5. {
   
6.     int i,j;
   
7.     for( i = 2*3*5*7*11*13*17*19; ; i++){
   
8.         j = 20;
   
9.         while( i % j == 0){
   
10.             if(j==1){
    
11.                 break;
    
12.             }
    
13.             j--;
    
14.         }
    
15.         if(j==1){
    
16.             printf("%d\n",i);
    
17.             break;
    
18.         }
    
19.     }
    
20.     return 0;
    
21. }

复制代码

由我们主宰

1. #include<stdio.h>
   
2. #include<math.h>
   
3. int g(int x)
   
4. {
   
5.         int i,j,z=1;
   
6.         for(i=2;i<=sqrt(x);i++)
   
7.         {
   
8.                 for(j=2;pow(i,j)<=x;j++)
   
9.                 {
   
10.                         z=pow(i,j);
    
11.                         if(x==z)
    
12.                         {
    
13.                                 return i;
    
14.                         }
    
15.                 }
    
16.         }
    
17.         return 0;
    
18. }
    
19. 
    
20. int f(int x)
    
21. {
    
22.         int i,y=1;
    
23.         for(i=1;i<=x;i++)
    
24.         {
    
25.                 if(y%i!=0)
    
26.                 {
    
27.                         if(g(i))
    
28.                         {
    
29.                                 y=y*g(i);
    
30.                         }
    
31.                         else
    
32.                         {
    
33.                                 y=y*i;
    
34.                         }
    
35.                 }
    
36.         }
    
37.         return y;
    
38. }
    
39. 
    
40. void main()
    
41. {
    
42.         int n=20;
    
43.         printf("%d\n",f(n));
    
44. }

复制代码

阿bang

1. def gcd(a, b):
   
2.     if a % b == 0:
   
3.         return b
   
4.     else:
   
5.         return gcd(b, a % b))
   
6. 
   
7. def minMuti(num):
   
8.     multi = 1
   
9.     for i in range(2, num + 1):
   
10.         multi = i * multi / gcd(i, multi)
    
11.     return multi
    
12. 
    
13. 
    
14. print minMuti(20)

复制代码

refracted_ray

1. """
   
2. 设这个最小值=m。显然，m=(2*3*5*7*11*13*17*19)*k，即m必然是20以内所有质数乘积的k倍，只需
   
3. 令k=1,2,3……，直到得到的m可以整除1-20所有数即可
   
4. """
   
5. 
   
6. x=2*3*5*7*11*13*17*19 # 20以内所有质数的乘积
   
7. k=1
   
8. stamp=True
   
9. while stamp:
   
10.         m=k*x
    
11.         flag=True # flag=True表示m可以整除1-20
    
12.         for i in range(2,21):
    
13.                 # 若当前的m值不能整除1-20，则k+1，跳出循环再来一次
    
14.                 if m % i!=0:
    
15.                         flag=False
    
16.                         k+=1
    
17.                         break
    
18. 
    
19.         # 当m可以整除1-20时，stamp置为False结束while循环
    
20.         if flag:
    
21.                 stamp=False
    
22. print ('能整除1-20的最小值是：%d'%m)

复制代码

答案是232792560

soulwyb

def main():
    minnum = 2520
    bool_ = True
    while True:
        for i in range(1, 21):
            if minnum % i != 0:
                minnum += 1
                bool_ = False
                break
        if bool_:
            print "最小数字为%d" % minnum
            break
        
main()


我是用手机码的 然后 手机卡死了 -_-

刘亮

题：求最小能被1-20中每个数都整除的最小正整数是多少？
手机编辑代码软件运行时间五秒之内
源代码：
#include<stdio.h>
#include<stdlib.h>

int  main()
{
     int  sum=0  ,   i   ;
     do{
               i=1;
               sum +=1;
               while(  sum%i  ==0  )
                          i++;
                }while(  i<=20 );
      printf("%d",sum);
      return 0;
     }
这段代码是在C4droid软件上测试运行成功的。
运行结果：232792560

ssd8661366

1. import time
   
2. import math
   
3. 
   
4. tStart = time.time()
   
5. 
   
6. def leastCommonMultiple(num):
   
7.     num = [s for s in range(1,num+1)]   #产生1~20 list
   
8.     div = []   
   
9.     ans = 1
   
10. 
    
11.     for count,i in enumerate(num):
    
12.         for j in range(count,len(num)): #检查后面所有数
    
13.             if num[j]%i == 0:   #若能整除
    
14.                 num[j]/=i       #除掉
    
15.         div.append(int(i))      #将除掉的数加入div[]
    
16.    
    
17.     for d in div:
    
18.         ans *= d
    
19.    
    
20.     return ans
    
21. 
    
22. 
    
23. print(leastCommonMultiple(20))
    
24. 
    
25. tEnd = time.time()
    
26. print ("花费 %.20f 秒" %(tEnd - tStart))
    

复制代码

答案：232792560
运行时间：0秒（无法测）

zzzgod

#include "stdafx.h"

#include <iostream>
#include <vector>
#include <algorithm>
#include <iterator>

using namespace std;

void div(vector<long long> & x, int num)
{
        int i = 2;
        while (i <= num)
        {
                while (num%i == 0)
                {
                        x.push_back(i);
                        num /= i;
                }
                i++;
        }
}

int main()
{
        vector<vector<long long>> tot;
        vector<long long> a, b;
        back_insert_iterator<vector<long long>> ib(b);
        int sum = 1;
        for (int i = 2; i <= 20; ++i)
        {
                tot.push_back({});
                div(tot[i - 2], i);
        }
        for (auto i : tot)
        {
                set_union(i.begin(), i.end(), a.begin(), a.end(),ib);
                a = b;
                b.clear();
        }
        for (auto i : a)
        {
                sum *= i;
        }
        cout << sum;
}

塔利班

1. from math import gcd
   
2. def fun(n):
   
3.     a=1
   
4.     for i in range(1,n+1):
   
5.         a=i*a//(gcd(a,i))
   
6.     return a
   
7. print(fun(20))

复制代码

茶侘酒寂

1. import sys
   
2. def f(x):
   
3.     temp = list(str(x))             #我用比较特别的方法判别回文数
   
4.     k = len(temp)
   
5.     while (k > (len(temp)/2)):
   
6.         if temp[j] != temp[k-1]:
   
7.             return False
   
8.         k -= 1
   
9.         j += 1
   
10.     return True
    
11. 
    
12. def g():                           
    
13.     k = 999
    
14.     for j in range(k,k//2,-1):
    
15.         for i in range(k,k//2,-1):
    
16.             print(j)
    
17.             if f(j*i):
    
18.                 return (j,i)
    
19. 
    
20. print(g())
    

复制代码

DetConan

ssd8661366 发表于 2018-5-5 00:18
答案：232792560
运行时间：0秒（无法测）

把time.time()改成time.clock()就可以了

shanczp

..挺简单的，就是运行时间需要2秒。从最小的1开始增加

1. 
   
2.     void oula_5(void)
   
3. {
   
4.         int num=1;
   
5.         for (int i = 1; i <= 20; )
   
6.         {
   
7.                 if(num%i==0)
   
8.                 {
   
9.                         if (i==20)
   
10.                         {
    
11.                         printf("%d\n",num);
    
12.                         return ;
    
13.                         }
    
14.                 i++;
    
15.                 }
    
16.                 else if(num%i!=0)
    
17.                 {
    
18.                         i=1;
    
19.                         num++;
    
20.                 }
    
21.         }
    
22. }
    
23.        

复制代码

Big_甲鱼

#第5题
#2520 是最小的能被 1-10 中每个数字整除的正整数。
#最小的能被 1-20 中每个数整除的正整数是多少？
#第一步求范围类的所有素数
import math
a=int(input('请输入一个正整数：'))
c=[]
for i in range(2,a+1):
    a1=0
    for each in range(2,i-1):      
        if i%each==0:
            a1=1
            break
    if a1==0:
        #print(i)
        c.append(i)
#第二步，求范围类有没有这些素数的倍数并装到字典中去
dic={}
for i2 in c:
    for i1 in range(1,a):   
        if i1%i2==0 and i1!=i2:
            dic[i2]=i1
#将字典中素数最大的倍数写进列表
list1=list(dic.values())
#用list1中每个数除以c的前位数相同的数求出kn
kn=[]
for xxoo in range(len(list1)):
    kn.append(int(math.log(list1[xxoo],c[xxoo])))
#最后计算结果
result=1
for ooxx in range(len(kn)):
    result*=c[ooxx]**kn[ooxx]
for oxox in range(len(kn),len(c)):
    result*=c[oxox]
print('{}是最小的能被 1-{}中每个数字整除的正整数。'.format(result,a))
终于完成了，代码很简单，就是讲公式分解之后一步步写回去的，优点就是计算速度还是相当快的！

cupbbboom

1. import time
   
2. print('开始计算')
   
3. start_time = time.time()
   
4. t = True
   
5. n = 20
   
6. while t:
   
7.         count = 0 # 记录20个数字是否都能整除，如果count=20，就说明能整除
   
8.         for i in range(1,21):
   
9.                 if n % i == 0:
   
10.                         count += 1
    
11.                 if count == 20:
    
12.                         result = n
    
13.                         t = False # 一算出结果就跳出while，即为最小
    
14.                         break
    
15. 
    
16.         n += 1   # n += 1 ,对最后结果没有影响，结果已经用result替代
    
17. print('最后结果为%s'%str(result))
    
18. end_time = time.time()
    
19. print('耗时：%s'%str(end_time - start_time))
    

复制代码

笨方法算
下面是结果：
开始计算
最后结果为232792560
耗时：1748.6437139511108