Euler第五题

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}\t\tRun 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

发表评论

无觅相关文章插件,快速提升流量