5
\$\begingroup\$

I wrote up a small script to calculate the answer to Project Euler Problem 5:

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'm wondering if this algorithm can be improved or made more efficient:

def divisible_by(num, den_set):
    if not den_set: return True
    elif not num % den_set.pop():
        return divisible_by(num, den_set)
    else: return False

def smallest(den_count):
    i = 1
    den_set = list(range(1, den_count))
    while not divisible_by(i, den_set):
        den_set = list(range(1, den_count))
        i += 1
    return i

print smallest(20)
\$\endgroup\$
2
  • 1
    \$\begingroup\$ In Python 2.7, range() already returns a list, so there’s no need to recast it. \$\endgroup\$ Commented Jul 6, 2015 at 6:55
  • \$\begingroup\$ @alexwlchan Thanks! I was thinking of Python 3, but then I managed to write Python 2 print statements... \$\endgroup\$ Commented Jul 6, 2015 at 23:31

2 Answers 2

Reset to default
4
\$\begingroup\$

The smallest number that can be divided by a set of numbers without any remainder is also known as the least common multiple, which can be calculated directly using the greatest common divisor (gcd).

The least common multiple of a, b:

lcm(a, b) = a * b / gcd(a, b)

The least common multiple of a, b, c:

lcm(a, b, c) = lcm(a, lcm(b, c))

You could generalize this to more numbers.

\$\endgroup\$
3
\$\begingroup\$

Use den_count += 1 before creating den_set. Because range(1, den_count) will create list of numbers from 1 to (den_count -1).
This is not a problem for 20, but for 25, your code will give an answer 5 times smaller than it should be (since you are skipping 25 itself).
Instead of checking whether each number satisfies the conditions, why not create the number. We know that the number has to divisible by every number from 1 to den_count.
If x is a number in the list then, let $$ den\_count = \alpha_1^{p_1} \times \alpha_2^{p_2}\times \alpha_3^{p_3}\times... $$ and $$ x = \alpha_1^{q_1} \times \alpha_2^{q_2} \times \alpha_3^{q_3} \times... $$ where, $$\alpha_1, \alpha_2, \alpha_3 ...$$ are prime numbers. Then it follows that,
$$ p_1 \geq q_1, p_2 \geq q_2, p_3 \geq q_3 ...$$ So we can factorize every number from 1 to den_count and take the largest values of $$q_1, q_2, q_3...$$ and construct the number easily.

\$\endgroup\$
2
  • \$\begingroup\$ In fact, [codereview.stackexchange.com/questions/35499/… uses same approach. Basically you want to find lcm of the numbers. \$\endgroup\$ Commented Jul 6, 2015 at 7:41
  • \$\begingroup\$ factoring isn't fast for large numbers. Algorithms based on gcd are much faster. \$\endgroup\$ Commented Jul 6, 2015 at 8:42

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.