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

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;
        }

感觉速度有点慢

运维小书童

#最小的能倍1-20 中每个数整除的正整数
#所求的数是1-20 中质数列表乘积的倍数
import time
start = time.clock()

def prime(param):
    '获得小于指定整数的质数列表'
    list = []
    for i in range(1,param+1):
        count = 0
        for j in range(2,i):
            if i%j == 0:
                count += 1
            if count > 1:
                break
        if count == 0:
            list.append(i)
    return(list)

def SmallestMutiple(number):
    '计算能被1-number中每个数整除的最小正整数，所求的数是1-number 中质数列表乘积的倍数'
    numplus = 1
    for each in prime(number):
        numplus *= each
    num = numplus
    while 1:
        temp = 0
        for each in range(1,number+1):
            if num%each !=0 :
                temp = 1
                break
        if temp == 0:
            return num
        else:
            num += numplus

print(SmallestMutiple(20))
end = time.clock()
print('耗时%f s'%(end - start))

麦特的灰

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

BngThea

orig = 1
for i in range(2,21):
    orig *= i

    
def check(num):
    for each in range(2,21):
        if not (num % each):
            return False
    return True

list1 = [2,3,5,7]

flage = True
while flage:
    result = orig
    for each in list1:
        orig //= each
        if not check(orig):
            orig *= each
            if result == orig:
                flage = False
            break
        
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编译：

import console;
import time.timer
 
console.setTitle("test");

time.timer.start();

var gcd = function(a,b){
        while a {
                a, b = b%a, a
        }
        return b
}

t = 1
for i=2;20;1 {
        t *= i/gcd(t,i);
}
console.print(t);
console.print(time.timer.endTick(), '毫秒');
console.pause();
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;
                }
        }
}

幻世伽蓝

#include <stdio.h>
#include <stdlib.h>

int main()
{
    int i,j;
    for( i = 2*3*5*7*11*13*17*19; ; i++){
        j = 20;
        while( i % j == 0){
            if(j==1){
                break;
            }
            j--;
        }
        if(j==1){
            printf("%d\n",i);
            break;
        }
    }
    return 0;
}

由我们主宰

#include<stdio.h>
#include<math.h>
int g(int x)
{
        int i,j,z=1;
        for(i=2;i<=sqrt(x);i++)
        {
                for(j=2;pow(i,j)<=x;j++)
                {
                        z=pow(i,j);
                        if(x==z)
                        {
                                return i;
                        }
                }
        }
        return 0;
}

int f(int x)
{
        int i,y=1;
        for(i=1;i<=x;i++)
        {
                if(y%i!=0)
                {
                        if(g(i))
                        {
                                y=y*g(i);
                        }
                        else
                        {
                                y=y*i;
                        }
                }
        }
        return y;
}

void main()
{
        int n=20;
        printf("%d\n",f(n));
}

阿bang

def gcd(a, b):
    if a % b == 0:
        return b
    else:
        return gcd(b, a % b))

def minMuti(num):
    multi = 1
    for i in range(2, num + 1):
        multi = i * multi / gcd(i, multi)
    return multi


print minMuti(20)

refracted_ray

"""
设这个最小值=m。显然，m=(2*3*5*7*11*13*17*19)*k，即m必然是20以内所有质数乘积的k倍，只需
令k=1,2,3……，直到得到的m可以整除1-20所有数即可
"""

x=2*3*5*7*11*13*17*19 # 20以内所有质数的乘积
k=1
stamp=True 
while stamp:
        m=k*x
        flag=True # flag=True表示m可以整除1-20
        for i in range(2,21):
                # 若当前的m值不能整除1-20，则k+1，跳出循环再来一次
                if m % i!=0:
                        flag=False
                        k+=1
                        break

        # 当m可以整除1-20时，stamp置为False结束while循环
        if flag:
                stamp=False
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

import time
import math 

tStart = time.time()

def leastCommonMultiple(num):
    num = [s for s in range(1,num+1)]   #产生1~20 list
    div = []    
    ans = 1

    for count,i in enumerate(num):
        for j in range(count,len(num)): #检查后面所有数
            if num[j]%i == 0:   #若能整除
                num[j]/=i       #除掉
        div.append(int(i))      #将除掉的数加入div[]
    
    for d in div:
        ans *= d
    
    return ans


print(leastCommonMultiple(20))

tEnd = time.time()
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;
}

塔利班

from math import gcd
def fun(n):
    a=1
    for i in range(1,n+1):
        a=i*a//(gcd(a,i))
    return a
print(fun(20))

茶侘酒寂

import sys
def f(x):
    temp = list(str(x))             #我用比较特别的方法判别回文数
    k = len(temp)
    while (k > (len(temp)/2)):
        if temp[j] != temp[k-1]:
            return False
        k -= 1
        j += 1
    return True

def g():                            
    k = 999
    for j in range(k,k//2,-1):
        for i in range(k,k//2,-1):
            print(j)
            if f(j*i):
                return (j,i)

print(g())

DetConan

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

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

shanczp

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

    void oula_5(void)
{
        int num=1;
        for (int i = 1; i <= 20; )
        {
                if(num%i==0)
                {
                        if (i==20)
                        {
                        printf("%d\n",num);
                        return ;
                        }
                i++;
                }
                else if(num%i!=0)
                {
                        i=1;
                        num++;
                }
        }
}