CODEWITHSUNDEEP
python
bard
bard

Reputation: 3052

Finding least common multiple of 5, 4, 3, 2, 1

So, I've written a little program to find the least common multiple of 5, 4, 3, 2, 1:

num = 1
multiples_list = []

for divisor in range(1,6):
    multiples_list.append(divisor)

multiple_5 = 5 * num
index = len(multiples_list) - 2

while index > 0:
    if multiple_5 % multiples_list[index] == 0:
        index -= 1
    else:
        num += 1
        index = len(multiples_list) - 2

if index == 0:
    print(multiple_5)

It seems that I've created an infinite loop... but why?

Upvotes: 0

Views: 561

Answers (4)

Paul Hankin
Paul Hankin

Reputation: 58201

I think your algorithm is: consider multiples of the largest number (here 5). Stop when this multiple is a multiple of all the numbers.

Here's how you might code that.

def lcm(*args):
    maxv = max(args)
    n = maxv
    while any(n % x for x in args):
        n += maxv
    return n

print lcm(1, 2, 3, 4, 5)

A massively useful way to debug code is to write tests before you start coding. This allows you to make sure that your code works in a variety of situations, and that when you see and fix one problem, you're not reintroducing bugs you've already fixed. I've a feeling that you've been debugging your code against the single example (1, 2, 3, 4, 5), and as a result you're a bit too focussed on the specifics of that.

Here's the actual test code I wrote to check the above code:

cases = [
    ((1, 2), 2),
    ((2, 3), 6),
    ((2, 4), 4),
    ((2, 3, 4), 12)
]
for xs, want in cases:
    if want != lcm(*xs): print('lcm(%s) = %s, want %s' % (xs, lcm(*xs), want))

Note, you don't need anything fancy, just a bunch of examples you know the answer to, and then run them and see if your code produces the same answer that you expect. Here it's just printing to the console if there's any discrepancies. As you get more sophisticated, you can use the unittest module, and have the tests separate, but for quick code when you're learning it's overkill.

Upvotes: 1

bard
bard

Reputation: 3052

I figured it out... the line 

multiple_5 = 5 * num

should have been inside the while loop, not outside of it. Because it was outside of the while loop, it never got updated when num was incremented.

Upvotes: 2

Philip Adler
Philip Adler

Reputation: 2206

Ok, let us step through the loop, one loop at a time to see what is going on.

loop 1:

index is 3, so multiples_list[index] will be 4

multiple_5 is 5, so multiple_5 % multiples_list[index] will be 1

1 is not equal to zero, so num will be incremented by 1, and index is set to 3

loop 2:

index is 3, so multiples_list[index] will be 4

multiple_5 is 5, so multiple_5 % multiples_list[index] will be 1

1 is not equal to zero, so num will be incremeneted by 1 and index is set to 3

loop 3:

index is 3, so multiples_list[index] will be 4

multiple_5 is 5, so multiple_5 % multiples_list[index] will be 1

1 is not equal to zero, so num will be incremeneted by 1 and index is set to 3

So you see, none of the loops are doing anything different, just steadily increasing the value of num, which you aren't testing for in the loop, ergo the loop continues ad. infinitum.

Upvotes: 1

TerryA
TerryA

Reputation: 59974

I think you're forgetting that indexes start at zero and not one.

while index > 0. At the beginning, index will be 3, because that is 5 - 2.

multiple_5 % multiples_list[index] == 0: will be False, because 5 % 4 == 1. Indexes start at zero, so multiples_list[3] is 4.

So then num increases by one, and index becomes len(multiples_list) - 2, which is 3, once again.

Upvotes: 0

Related Questions