Explore our sites

Stack Exchange
tour help careers 2.0
Take the tour ×
Stack Overflow is a question and answer site for professional and enthusiast programmers. It's 100% free, no registration required.
up vote 3 down vote favorite

I'm currently trying to work through the ProjectEuler questions with Python (something I've only picked up today). The question I'm working is question 5, where

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 worked through the problems using Java before, so using the same method as I did before, I just created a loop that iterated, however it seems that my code never ends.

Python:

i = 1
while 1:
    if i%2 == 0 and i%3==0 and i%4==0 and i%5==0 and i%6==0 and i%7==0 and i%8==0 and i%9==0 and i%10==0 and i%11==0 and i%12==0 and i%13==0 and i%14==0 and i%15==0 and i%16==0 and i%17==0 and i%18==0 and i%19==0:
        print i
        break
    i+=1

Java:

public class p5
{
    public static void main(String[] args)
    {
        for (int i=1;;i++)
        {
            if (i%1==0&&i%2==0&&i%3==0&&i%4==0&&i%5==0&&i%6==0&&i%7==0&&i%8==0&&i%9==0&&i%10==0&&i%11==0&&i%12==0&&i%13==0&&i%14==0&&i%15==0&&i%16==0&&i%17==0&&i%18==0&&i%19==0&&i%20==0)
            {
                System.out.println(i);
                break;
            }
        }
    }
}

Java executed that in under 3 seconds on my computer, whereas the Python code never seemed to end. Any tips?

Edit:

Apparently I typed something wrong, which caused it to never end. However, even with the entire thing written correctly (with the same output as my Java), it still took 1 minute and 20 seconds, whereas for Java it took around 1 - 2 seconds. Am I doing anything wrong? Or is Python's performance that bad (which shouldn't be afaik)

share|improve this question
 
As an aside, this is not the algorithm that should be used to solve this problem. –  Ignacio Vazquez-Abrams Oct 24 '12 at 17:57
 
Is this project euler? –  Ashwini Chaudhary Oct 24 '12 at 18:33
add comment

migrated from codereview.stackexchange.com Oct 24 '12 at 17:16

This question came from our site for peer programmer code reviews.

2 Answers

up vote 4 down vote accepted

Arithmetics with primitive ints is much faster in Java then with full integer objects in CPython i.e., the performance difference of 30 times that you see is not surprising for your code.

Note the algorithm is very inefficient and it won't work for a slightly larger input e.g., for numbers from 1 to 50 (It takes too long and the correct result is larger than max int/long in Java).

It takes ~100 micro-seconds to compute the result for all numbers from 1 to 100 on my machine with a more efficient algorithm:

#!/usr/bin/env python
from functools import reduce

def gcd(a, b):
    """Greatest common divisor (factor)."""
    while b: # Euclid's algorithm
        a, b = b, a % b
    return a

def lcm(*args):
    """Least common multiple."""
    # lcm(a, b, c) == lcm(lcm(a, b), c)
    return reduce(lambda a, b: a * b // gcd(a, b), args)

def f(n):
    """Smallest positive number evenly divisible by all numbers from 1
       to n including.
    """
    return lcm(*range(1, n + 1))

print(f(10)) # -> 2520
print(f(50)) # -> 3099044504245996706400

To estimate the performance:

#!/usr/bin/env python
import timeit
from functools import partial

def measure():
    for n in [10, 50, 100]:
        print("%d: %5.2f microseconds" % (n, timeit.timeit(partial(f, n),
                                                           number=1000*1000)))
measure()
share|improve this answer
 
Thanks I do realize that my method isn't the most efficient way of doing things, but my question was more of why python takes around 60+ times longer than Java despite using the same code, but I guess you did sort of answer the question in your first sentence, so I'll mark it as correct –  TheAmateurProgrammer Oct 25 '12 at 1:42
add comment
up vote 2 down vote

My pure bruteforce solution takes ~250 ms using pypy:

i = 20
while 1:
    if i%20 == 0 and i%19==0 and i%18==0 and i%17==0 and i%16==0 and i%15==0 and i%14==0 and i%13==0 and i%12==0 and i%11==0:
        print i
        break
    i+=20

More elegant should use something like greatest common divisors and least common multiples.

share|improve this answer
 
You should be able to just use the primes from 1-20 right? –  Kort Pleco Oct 24 '12 at 18:45
 
Nope: 4 divides evenly into 2, but not 8, for example. You need the maximum power of each prime between 1 and 20: ie, 19, 17, 16, 13, 11, 9, 7, and 5. –  Tom Johnson Oct 26 '12 at 13:51
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.