[Tutor] To find the least number divisible by all numbers from 1-20

[#PATHANGI JANARDHANAN JATINSHRAVAN#]

________________________________________
From: Tim Peters [tim.peters at gmail.com]
Sent: Wednesday, August 14, 2013 02:35 AM
To: #PATHANGI JANARDHANAN JATINSHRAVAN#
Cc: tutor at python.org; N_Gopalakrishnan at Dell.com; pathangi_janardhanan at dell.com
Subject: Re: [Tutor] To find the least number divisible by all numbers from 1-20

[#PATHANGI JANARDHANAN JATINSHRAVAN#]
> ///
> I am solving problem number 5 in project euler. I think my solution seems
> logically correct but it is not giving an answer as it is taking too long to
> execute.

It does take a long time, but it does return the correct answer - eventually ;-)

> So can someone suggest an alternative solution? Here is my source
> code:
>
> import sys
> def check(num):
>   lis=[20,19,18,17,16,14,13,11]  #because a no. divisible by 20 is divisible
> by 2,4,5 and so on for the values omitted
>   for i in lis:
>     if num%i==0:
>       continue
>     else:
>       return False
>       break
>
>   return True

Simpler:

    def check(num):
      return all(num % i == 0 for i in [20,19,18,17,16,14,13,11])

> def main():
>   num=2520  # Because we can start from the no. divisible by 1-10
>   while not check(num):
>     print(num)
>     num+=2    # Because num has to be even

You can speed this up by a factor of about 1000 via incrementing by
2520 instead of by 2.  Because the correct answer has to be divisible
by all of 1 thru 10, it has to be divisible by 2520 too, right?
Therefore the correct answer must be a multiple of 2520.

 Incrementing  by 2520 drastically speeds up the execution time. Thanks, I didn't think of that. And I'm still trying to comprehend the LCM and GCD methods. I'm pretty new to programming and python. 

>   print(num)

Peter is on "the best" track via exploiting this fact:

    lcm(a, b) = a * b // gcd(a, b)

The problems he hit with recursion can be avoided by using an
iterative gcd function instead.  Like so:

def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

def lcm_list(ns):
    sofar = 1
    for n in ns:
        sofar = sofar * n // gcd(sofar, n)
    return sofar

Then:

>>> print lcm_list(range(1, 21))  # your case
232792560

That takes a small fraction of a second.  So does this:

>>> print lcm_list(range(1, 101))
69720375229712477164533808935312303556800

Even this takes a fraction of a second!:

>>> print lcm_list(range(1, 1001))
7128865274665093053166384155714272920668358861885893040452001991154324087581111499476444151913871586911717817019575256512980264067621009251465871004305131072686268143200196609974862745937188343705015434452523739745298963145674982128236956232823794011068809262317708861979540791247754558049326475737829923352751796735248042463638051137034331214781746850878453485678021888075373249921995672056932029099390891687487672697950931603520000

Amazing, eh?  :-)