题目5：找出最小的能被1-20中每个数整除的数,欧拉计划（Project Euler）,数据结构与算法,鱼C论坛

运维小书童 发表于 2017-8-4 15:38:43

#最小的能倍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))

麦特的灰 发表于 2017-9-2 09:18:06

#找出最小的能被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 发表于 2017-9-11 17:13:39

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 =

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 发表于 2017-9-27 21:48:57

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 =
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) ** int(NumCList))

print(Smallsum)
end = time.clock()
print("运行时间:%fs" %(end - start))

该数组所有的质数是:
每个质数对应的次幂:
232792560
运行时间:0.001115s

jerryxjr1220 发表于 2017-9-29 17:08:04

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 发表于 2018-1-4 15:27:24

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

幻世伽蓝 发表于 2018-1-10 16:14:57

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

由我们主宰 发表于 2018-3-5 15:45:32

#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 发表于 2018-3-26 17:22:55

本帖最后由阿bang 于 2018-3-26 17:27 编辑

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 发表于 2018-4-13 23:28:07

本帖最后由 refracted_ray 于 2018-4-13 23:29 编辑

"""
设这个最小值=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 发表于 2018-4-16 19:56:32

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()

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

刘亮发表于 2018-4-25 09:49:12

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

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

ssd8661366 发表于 2018-5-5 00:18:42

import time
import math

tStart = time.time()

def leastCommonMultiple(num):
num = #产生1~20 list
div = []
ans = 1

for count,i in enumerate(num):
   for j in range(count,len(num)): #检查后面所有数
         if num%i == 0: #若能整除
            num/=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 发表于 2018-6-20 18:13:41

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

塔利班 发表于 2018-8-23 17:19:01

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))

茶侘酒寂 发表于 2018-8-26 17:55:11

import sys
def f(x):
temp = list(str(x))          #我用比较特别的方法判别回文数
k = len(temp)
while (k > (len(temp)/2)):
   if temp != temp:
         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 发表于 2018-9-3 17:39:39

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

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

shanczp 发表于 2018-10-10 20:00:17

..挺简单的，就是运行时间需要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++;
}
}
}

Big_甲鱼 发表于 2018-10-14 21:15:10

#第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=i1
#将字典中素数最大的倍数写进列表
list1=list(dic.values())
#用list1中每个数除以c的前位数相同的数求出kn
kn=[]
for xxoo in range(len(list1)):
kn.append(int(math.log(list1,c)))
#最后计算结果
result=1
for ooxx in range(len(kn)):
result*=c**kn
for oxox in range(len(kn),len(c)):
result*=c
print('{}是最小的能被 1-{}中每个数字整除的正整数。'.format(result,a))
终于完成了，代码很简单，就是讲公式分解之后一步步写回去的，优点就是计算速度还是相当快的！

cupbbboom 发表于 2018-11-21 18:16:49

import time
print('开始计算')
start_time = time.time()
t = True
n = 20
while t:
count = 0 # 记录20个数字是否都能整除，如果count=20，就说明能整除
for i in range(1,21):
if n % i == 0:
count += 1
if count == 20:
result = n
t = False # 一算出结果就跳出while，即为最小
break

n += 1 # n += 1 ,对最后结果没有影响，结果已经用result替代
print('最后结果为%s'%str(result))
end_time = time.time()
print('耗时：%s'%str(end_time - start_time))

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

页: 1 2 [3] 4 5 6

鱼C论坛's Archiver