Project Euler: problem 5

This was the problem that first attracted my attention to Project Euler, after reading about it on the Daily WTF.

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 number that is evenly divisible by all of the numbers from 1 to 20?

Rather than try doing it with multiple nested MOD statements, I thought it made more sense to do it properly as a loop. Took me a few goes to get this one right. I kept going into infinite loops because I was stepping too far; the reason I don’t like using while loops.

<cfset found = 0>
<cfset step = 20>
<cfset factor = step - 1>
<cfset i = step>

<cfloop condition="NOT found">
	<cfoutput>#i#<br></cfoutput>
	<cfif NOT i MOD factor>
	<!--- factor goes into i exactly --->
		<hr>
		<!--- it must be a multiple of this number --->
		<cfif factor EQ 11>
			<cfset found = 1>
			<cfbreak>
		</cfif>
		
		<cfset factor = factor - 1>	
		<!--- each successful iteration, step down once --->
		<cfset step = i>
		<cfoutput>step = #step#, factor = #factor#<br></cfoutput>
	<cfelse>
		<cfset i = i + step>
	</cfif>
</cfloop>

<cfoutput><strong>#i#</strong></cfoutput>

There’s a little bit of redundancy in the loop; as I’m using <cfbreak>, I don’t need to also set my ‘found’ flag to true, as the loop will end anyway. In fact the loop might just as well say condition=”1 GT 0″, as I’m wanting to loop forever until we get that last factor.

In the document you can access after solving this problem, it goes into using prime factors and logarithms and various complicated mathematical ways to do the same thing, but I like to keep it simple.

Basically we start at 20 (although I could have started at 2520), incrementing by 20 each time. First try doing MOD 19 (we don’t need to bother with MOD 20 because we already know it’s a multiple of 20). Once we’ve got a number that both 19 and 20 are factors for, we increase our increment from 20 to whatever this number is. Repeat in that fashion until we hit a number that satisfies MOD 11. We don’t need to bother with 1-10, because all those numbers are already factors of numbers from 11-20.