Euler 5: Smalest number that can be divided by numbers from 1 to 20

Question

I m trying to solver Problem 5 in projecteuler.The problem is as follows

2520 is the smallest number that can be divided by each of the numbers from 1 to 10 without any remainder.

What is the smallest positive number that is evenly divisible by all of the numbers from 1 to 20?

I have written a simple python program

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

#function returns the list of prime factors of 'n'
def find_pf(n):
        pf = []
        for j in primes:
                if i % j == 0:
                        pf.append(j)

        return pf

#multiplies all the prime factors of all the numbers 
#from 1[1..20]
for i in range(1,21):
        lst = find_pf(i)
        for i in lst:
                prod *= i 


#verifies that 'n' is diviible evenly by [1..20]
count = 0
def test_n(n):
        global count
        for i in range(1,21):
                if n % i != 0:
                        count += 1


print ('smallest number divisible by [1..20] {}'.format(prod))
test_n(prod)
print('Total failures {}'.format(count))

The result obtained by the above program is

smallest number divisible by [1..20] 1055947052160000
Total failures 0

The answer 1055947052160000 is incorrect.? Can someone kindly point out what is wrong with the above program? Or suggest the correct method to solve this problem?

See e.g. http://stackoverflow.com/questions/8024911/project-euler-5-in-python-how-can-i-optimize-my-solution?rq=1 — Fredrik Pihl, May 05 '14 at 07:22

score 3 · Answer 1 · answered May 05 '14 at 07:29

The error is in

#multiplies all the prime factors of all the numbers 
#from 1[1..20]
for i in range(1,21):
    lst = find_pf(i)
    for i in lst:
            prod *= i

You are only interested in the highest necessary power of any prime. For example, the value you are looking for shall be divisible by 16. Your code looks for a number divisible by 2*4*8*16.

score 2 · Accepted Answer · edited Apr 16 '15 at 07:34

2

Your code is looking for too many primes. It is enough to look for the greatest: e.g. if the number is dividable by 16, it is already dividable by 8.

primes = [2,3,5,7,11,13,17,19]
prod = 1 
for p in primes:
    n = 2
    prod *= p
    while (p**n < 21):
        prod *= p
        n += 1

print prod

Here you get

232792560

edited Apr 16 '15 at 07:34

Rob Van Dam

7,812
3
31
34

answered May 05 '14 at 07:54

yoopoo

343
1
2
10

Padraic Cunningham · Answer 3 · 2014-05-05T07:49:13.343

def lcm(*values):
    values = [value for value in values]
    if values:
        n = max(values)
        m = n
        values.remove(n)
        while any(n % value for value in values):
            n += m
        return n
    return 0

    reduce(lcm, range(1, 20))
In [3]: reduce(lcm, range(1, 20))
Out[3]: 232792560

reduce applies " function of two arguments cumulatively to the items of iterable from left to right, so as to reduce the iterable to a single value."

 def add_nums(a,b):
    print a,b # added print to show values
    return a+b
 reduce(add_nums, [1, 2, 3, 4, 5]) #calculates ((((1+2)+3)+4)+5)

what is reduce() function? what does it do? – liv2hak May 05 '14 at 07:35 — liv2hak, May 05 '14 at 07:35

score 0 · Answer 4 · answered Apr 26 '23 at 00:44

0

I got a good method for this and answer is coming correct. Check it out here

As answer is also coming correct which is:232792560

answered Apr 26 '23 at 00:44

techie world

1

1

Please read [Why should I not upload images of code/data/errors?](https://meta.stackoverflow.com/q/285551/354577) Instead, format code as a [code block]. The easiest way to do this is to paste the code as text directly into your question, then select it and click the code block button. – ChrisGPT was on strike Apr 26 '23 at 22:18

Euler 5: Smalest number that can be divided by numbers from 1 to 20

4 Answers4