Project Euler getting smallest multiple in python
Solution 1
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
Solution 2
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
)
Solution 3
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);
}
Solution 4
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)
Related videos on Youtube
Comments
-
Padraic Cunningham over 1 year
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))
-
Padraic Cunningham over 10 yearsI improved my code my increasing i by 20 each time and got the correct answer but still trying to figure out an alternative method.
-
Padraic Cunningham over 10 yearswhat does sys.maxint do? I have looked it up in the docs but it is still unclear to me.
-
hughdbrown over 10 yearsThis is a really good answer. It's really short and works. My answer is clumsy by comparison.
-
Padraic Cunningham over 10 years@Colonel panic, Thanks, I added a function
def allLcms(*args):
``return reduce(lcm1, args)` -
Padraic Cunningham over 10 years@Colonel panic, sorry, I could not edit previous comment. Thanks for your help, I solved it using your advice.
-
davecom over 10 yearsIt provides the maximum integer value available. xrange() as opposed to range() will ensure you don't actually create a range that goes all the way to it!
-
Padraic Cunningham over 10 yearsThanks, so xrange acts like a generator?
-
Filipe Barreto Peixoto Teles almost 9 yearsI'm not fulling grasping the last bit. Reduce will apply the lcm function use the range from 1 to 20, starting with 1, 2 then 2, 3 then 3, 4 etc. The sum of all that calculated lcm() is the answer, is that it? I'm confused.