CODEWITHSUNDEEP
python
liv2hak
liv2hak

Reputation: 15010

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

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?

Upvotes: 0

Views: 2988

Answers (4)

techie world
techie world

Reputation: 1

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

Upvotes: 0

yoopoo
yoopoo

Reputation: 363

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

Upvotes: 2

Padraic Cunningham
Padraic Cunningham

Reputation: 180540

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)

Upvotes: 1

user58697
user58697

Reputation: 7923

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.

Upvotes: 3

Related Questions