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

[Peter Otten]

#PATHANGI JANARDHANAN JATINSHRAVAN# wrote:

> Hello All,
> 
> Sorry for the earlier mail without subject. I was in a hurry so I missed
> that
> 
> 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. 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
> 
> 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
>   print(num)
> 
> 
> if __name__ == '__main__':
>   main()

A simple algorithm that I think should work:

Start with the list of 19 numbers (no need to include the 1). 

Pick two numbers a and b, calculate the (greatest common divisor) gcd, and 
replace them with the single number c calculated as

d = gcd(a, b)
c = a*b//d

until there is only one number left in the list. This should be your result.
I'll post a naive implementation of that idea in a follow-up.