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

776667 · 发表于 2016-10-6 00:04:02

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 · 发表于 2016-10-6 21:07:04

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 · 发表于 2016-10-10 14:44:56

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)

复制代码

梦想绘制者 · 发表于 2016-11-3 00:29:05

哎，写这个程序费了好久。
这个题目其实就是求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 · 发表于 2016-11-7 22:26:18

#找出能被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 · 发表于 2016-11-9 11:06:19

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 · 发表于 2016-11-18 00:39:17

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

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

芒果加黄桃 · 发表于 2017-1-7 00:48:28

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

复制代码

渡风 · 发表于 2017-1-12 22:13:45

本帖最后由渡风于 2017-1-12 22:15 编辑

此代码使用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 · 发表于 2017-2-2 13:51:20

'''
思路:
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。

夜魔时生 · 发表于 2017-3-6 14:19:44

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

复制代码

99592938 · 发表于 2017-3-14 15:32:17

先把所有质数挑出来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 · 发表于 2017-3-14 15:35:30

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

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

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

#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 · 发表于 2017-3-27 10:49:40

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 · 发表于 2017-4-16 21:29:22

#求能被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

天之南 · 发表于 2017-4-30 21:34:56

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

复制代码

铭记太阳 · 发表于 2017-5-4 16:39:09

答案是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 · 发表于 2017-5-6 22:23:28

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

复制代码

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

格式化、 · 发表于 2017-6-7 15:38:48

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

复制代码

感觉速度有点慢

账号		自动登录	找回密码
密码			立即注册