4
\$\begingroup\$

I have just started learning python and I am solving Project Euler problems alongside for practice. This is my solution for problem 5. Project Euler asks for the minimum value divisible by all numbers from 1 to 20 but I have made the program so it works from 1 to n.

I think there is a lot of room for improvement in it and I need your suggestions. Please tell me how I can improve it.

def least(x):
    """
    Variables:
    x = Argument of function and the maximum value of range.
    n = Number that is going to be tested by loops in each cycle.
    a = Number that is going to be added to "n" in each cycle of loop. It is initialized with "x".
        For example: if we check for all numbers from 1 to 10, each "n" has to be multiple of 10. So that's why
        a will be added to n in each turn.
    y = To minimize machine time, I have tried to bring argument of "least" function below 10.
        So if x is bigger than 10, y will be x - 10. And then we will do recursion and use "least" on y.

        For example: If we check from 1 to 40.
            least(40) -> n = least(30) = a                          (calls least(30) to get n and a)
                least(30) -> n = least(20) = a                      (calls least(20) to get n and a)
                    least(20) -> n = least(10) = a                  (calls least(10) to get n and a)
                        least(10) -> n = 10, a =10, (Brute Check)
                            (Brute Check)
        (At each stage "for loop" checks "n" in each loop cycle and adds "a" until value found.)
    """
    if x <= 10:
        n = x #The first number to test
        a = x #a is number that's going to be added in each turn
    else:
        y = x - 10
        n = least(y) #Recursion to minimize machine load and time
        a = n
    while True:
        d = 0
        for i in range(1,x + 1):
            if n % i == 0:
                d += 1 #counts if i evenly divides.
            else:
                break #Checks each n. If i doesn't evenly divide, skips loop cycle.
        if d == x: #if each "i" divides evenly, d will be equal to x and thus minimum value will be n.
            return n
        else:
            n += a #adds a(specified above)
minimumvalue = least(int(input("Minimum Value divisible by all integers from 1 to n.\n Specify n: ")))
print(" Minimum Value: " + str(minimumvalue))

Github Link

\$\endgroup\$
  • \$\begingroup\$ The github link doesn''t work (anymore ?) \$\endgroup\$ – SylvainD Jun 1 '15 at 19:46
  • \$\begingroup\$ I am very sorry. I reorganized the solutions into another folder making this link invalid. I have fixed it. \$\endgroup\$ – Waqas Jun 3 '15 at 4:37
4
\$\begingroup\$

Your code can be more pythonic.

  1. Names of variables and functions should be more meaningful and descriptive. Also - read PEP8.
  2. You should encapsulate your code in smaller functions responsible for one thing. And signal what is the purpose of each function by it's name (= meaningful names).
  3. Use power which python gives you. To save memory instead of range() use xrange() in every case when you only need to iterate over. range() creates a list, so if you do range(1, 99999) it creates a list in memory with 99999 elements. In contrast xrange() is a sequence object that evaluates lazily.
  4. There are more efficient algorithms than brute-force. But even your brute-force approach can be improved. With xranege() you don't need recursion any more. What is more it's wiser to iterate over dividers in decreasing order. Which is dead simple in python, just use -1 as third xrange() parameter (step).

Take a look at this example:

def smallest_common_multiple(maximal_divisor):
    for number in xrange(maximal_divisor, sys.maxsize):
        if is_common_multiple(number, maximal_divisor):
            return number

def is_common_multiple(number, maximal_divisor):
    for divisor in xrange(maximal_divisor, 1, -1):
        if number % divisor != 0:
            return False
    return True

Comment:

In smallest_common_multiple() iteration starts from maximal_divisor because smaller numbers doesn't make sense. sys.maxsize works like to infinity.

:-)

Update

As Josay points out this can be even simpler. Thanks Josay!

from itertools import count

def smallest_common_multiple(maximal_divisor):
    for number in count(maximal_divisor):
        if is_common_multiple(number, maximal_divisor):
            return number

def is_common_multiple(number, maximal_divisor):
    return all([number % divisor == 0 for divisor in xrange(maximal_divisor, 1, -1)])
| improve this answer | |
\$\endgroup\$
3
\$\begingroup\$

Monolithic function

You should separate yuor code into smaller functions.

Meaningful names

You have extensive comments but the names are cryptic, I would remove some of the comments and use more self describing names.

Avoid brute force

You should always look for an alternative approach rather than brute-force. I will not spoil you the full answer but the smallest_common_multiple may help you...

| improve this answer | |
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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