Project Euler Problem #5

Ok, I really wanted to do this problem by hand. It reminds me of a programming course I taught a few years ago. One of the assignments for the students was to write a program that printed out the sum of the integers from 1 to 100. One of my more clever students submitted a one-line program:

print 5050

He got points for cleverness!

But I’m working on programming so I’ll avoid solutions like that for now. Here’s the problem:

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?

And here’s my solution:

def islcm(n):
	for d in range(1,21):
		if n % d != 0:
			return False
	return True

n = 2*3*5*7*11*13*17*19
p = n

while not islcm(p):
	p = p + n

print p

232,792,560 is the least common multiple of the numbers from 1 to 20, verified by WolframAlpha (see the last line under properties).

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>