Euler第五题：

求1到20各数的最小公倍数。

目前我用的方法是按照短除法求最小公倍数的方法做的。Euler给出的方法虽然原理基本搞懂，但是编程还没有实现。

——————————————————————————————————-

def primeNumber(k):

primes=[2,3,5,7,11,13,17,19]

number=21

while number<k:

flag=True

for prime in primes:

if number%prime==0:

flag=False

break

if flag:

primes.append(number)

number=number+2

return primes

def smallestMulti(z):

dividends=[]

for i in range(z):

dividends.append(i+1)

print(“{0}n{1}”.format(dividends,”–“*2*len(dividends)))

dividers=primeNumber(z)

print(“{0}n{1}”.format(dividers,”–“*2*len(dividers)))

divisors=[]

for divider in dividers:

flag=True

while flag:

for i in range(len(dividends)):

if dividends[i]%divider==0:

flag=True

divisors.append(divider)

break

else:

flag=False

for i in range(len(dividends)):

if dividends[i]%divider==0:

dividends[i]=dividends[i]//divider

# print(dividends)

print(“{0}n{1}”.format(divisors,”–“*2*len(divisors)))

answer=1

for divisor in divisors:

answer=answer*divisor

return answer

if __name__==”__main__”:

from time import clock

start=clock()

z=20

# print(smallestMulti(z))

print(“The answer is: {0}ttRun time: {1:.6f}s”.format(smallestMulti(z),clock()-start))

————————————————————————————————————

结果：

[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20]

——————————————————————————–

[2, 3, 5, 7, 11, 13, 17, 19]

——————————–

[2, 2, 2, 2, 3, 3, 5, 7, 11, 13, 17, 19]

————————————————

The answer is: 232792560 Run time: 0.000390s