Project Euler getting smallest multiple in python

Question

I am doing problem five in Project Euler: "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 constructed the following code which finds the correct value 2520 when using 1 - 10 as divisors but code seems to be going on forever when using 1 - 20. Again I don't want the code just a pointer or two on where I am going wrong. Thanks

def smallestDiv(n):
    end=False
    while end == False:
        divisors = [x for x in range(1,21)]    # get divisors
        allDivisions = zip(n % i for i in divisors)    # get values for  n % all integers in divisors
        check = all(item[0]  == 0 for item in allDivisions )   # check if all values of n % i are equal to zero
        if check:         # if all values are equal to zero return n
            end = True
            return n
        else:             # else increase n by 1
            n +=1

EDIT:

I used some code I found relating to LCM and used reduce to solve the problem:

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

print reduce(lcm, range(1,21))

Answer 1

If you can use math module, you can use math.lcm

import math
def smallestMul():
    return(math.lcm(1, 2, 3, ..., 20))

Answer 2

I think the answer by Colonel Panic is brilliant but I just wanted to expand on it a little bit without editing the concise answer.

The original solution is:

from fractions import gcd
def lcm(a,b):
    "Calculate the lowest common multiple of two integers a and b"
    return a*b//gcd(a,b)

>>> from functools import reduce
>>> reduce(lcm, range(1,10+1))
2520
>>> reduce(lcm, range(1,20+1))
232792560

I find it helpful to visualize what the reduce is doing for N = 10:

res = lcm(lcm(lcm(lcm(lcm(lcm(lcm(lcm(lcm(1, 2), 3), 4), 5), 6), 7), 8), 9), 10)

Which evaluates to:

# Evaluates lcm(1, 2)
res = lcm(lcm(lcm(lcm(lcm(lcm(lcm(lcm(lcm(1, 2), 3), 4), 5), 6), 7), 8), 9), 10)
# Evaluates lcm(2, 3)
res = lcm(lcm(lcm(lcm(lcm(lcm(lcm(lcm(2, 3), 4), 5), 6), 7), 8), 9), 10)
# Evaluates lcm(6, 4)
res = lcm(lcm(lcm(lcm(lcm(lcm(lcm(6, 4), 5), 6), 7), 8), 9), 10)
# Evaluates lcm(12, 5)
res = lcm(lcm(lcm(lcm(lcm(lcm(12, 5), 6), 7), 8), 9), 10)
# Evaluates lcm(60, 6)
res = lcm(lcm(lcm(lcm(lcm(60, 6), 7), 8), 9), 10)
# Evaluates lcm(60, 7)
res = lcm(lcm(lcm(lcm(60, 7), 8), 9), 10)
# Evaluates lcm(420, 8)
res = lcm(lcm(lcm(420, 8), 9), 10)
# Evaluates lcm(840, 9)
res = lcm(lcm(840, 9), 10)
# Evaluates lcm(2520, 10)
res = lcm(2520, 10)

print(res)
>>> 2520

The above gets across the intuition of what is happening. When we use reduce we "apply a rolling computation to sequential pairs of values in a list." It does this from the "inside-out" or from the left to the right in range(1, 20+1).

I think it is really important here to point out that you, as a programmer, are NOT expected to intuit this answer as being obvious or readily apparent. It has taken a lot of smart people a long time to learn a great deal about prime numbers, greatest common factors, and least common multiples, etc. However, as a software engineer you ARE expected to know the basics about number theory, gcd, lcm, prime numbers, and how to solve problems with these in your toolkit. Again, you are not expected to re-invent the wheel or re-discover things from number theory each time you solve a problem, but as you go about your business you should be adding tools to your problem solving toolkit.

Answer 3

Last function finds the smallest number dividable by n, since the number should be multiples of factorial(n), you need to have a function that calculates factorial (can be done via math. method)

def factoral(n):
    if n > 1:
        return n * factoral(n - 1)
    elif n >= 0:
        return 1
    else:
        return -1

def isMultiple(a, b):
    for i in range(1, b):
        if a % i != 0:
            return False
    return True

def EnkucukBul(n):
    for i in range(n, factoral(n) + 1, n):
        if isMultiple(i, n):
            return i
    return -1

Answer 4

facList=[2]
prod=1

for i in range(3,1000):
    n=i
    for j in facList:
        if n % j == 0:
            n//=j
    facList.append(n)

for k in facList:
prod*=k

print(prod)

I tried this method and compared my time to Colonel Panic's answer and mine started significantly beating his at about n=200 instead of n=20. His is much more elegant in my opinion, but for some reason mine is faster. Maybe someone with better understanding of algorithm runtime can explain why.

Answer 5

int gcd(int m, int n)
{
    int t;
    while(n!=0)
    {
        t=n;
        n=m%n;
        m=t;
    }
    return m;
}

#include<stdio.h>
int main()
{
    int i,n;
    int long long lcm=1;
    printf("Enter the range:");
    scanf("%d",&n);
    for (i=1;i<=n;i++)
    {
        lcm = (i*lcm)/gcd(i,lcm);
    }
    printf("smallest multiple : %uL",lcm);

}

Answer 6

If a problem is hard, trying solving a simpler version. Here, how to calculate the lowest common multiple of two numbers. If you've read any number theory book (or think about prime factors), you can do that using the greatest common divisor function (as implemented by the Euclidean algorithm).

from fractions import gcd
def lcm(a,b):
    "Calculate the lowest common multiple of two integers a and b"
    return a*b//gcd(a,b)

Observing lcm(a,b,c) ≡ lcm(lcm(a,b),c) it's simple to solve your problem with Python's reduce function

>>> from functools import reduce
>>> reduce(lcm, range(1,10+1))
2520
>>> reduce(lcm, range(1,20+1))
232792560

Answer 7

This will give you all the factors in the numbers from 1 to 20:

from collections import Counter

def prime_factors(x):
    def factor_this(x, factor):
        factors = []
        while x % factor == 0:
            x /= factor
            factors.append(factor)
        return x, factors
    x, factors = factor_this(x, 2)
    x, f = factor_this(x, 3)
    factors += f
    i = 5
    while i * i <= x:
        for j in (2, 4):
            x, f = factor_this(x, i)
            factors += f
            i += j
    if x > 1:
        factors.append(x)
    return factors

def factors_in_range(x):
    result = {}
    for i in range(2, x + 1):
        p = prime_factors(i)
        c = Counter(p)
        for k, v in c.items():
            n = result.get(k)
            if n is None or n < v:
                result[k] = v
    return result

print factors_in_range(20)

If you multiply these numbers together, as many times as they occur in the result, you get the smallest number that divides all the numbers from 1 to 20.

import operator

def product(c):
    return reduce(operator.__mul__, [k ** v for k, v in c.items()], 1)

c = factors_in_range(20)
print product(c)

Answer 8

import sys

def smallestDiv(n):
    divisors = [x for x in range(1,(n+1))]    # get divisors
    for i in xrange(2520,sys.maxint,n):
        if(all(i%x == 0 for x in divisors)):
            return i

print (smallestDiv(20))

Takes approximately 5 seconds on my 1.7 GHZ i7

I based it on the C# code here: http://www.mathblog.dk/project-euler-problem-5/

Answer 9

You are doing a brute force search, so it can get arbitrary long. You should read about LCM (least common multiple) in order to code an efficient solution.(which I believe is 232792560)