Duncan's blog

October 23, 2008

Project Euler: problem 5

Filed under: Coldfusion,Project Euler — duncan @ 7:00 am
Tags: , , , ,

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.

2 Comments »

  1. That solution is still pretty terrible. You should be able to find the answer with a few minutes of pencil and paper calculation. Hint: what is the smallest number divisible by both 40 and 60? Use the same approach for 1,2,3…20.

    Comment by solrize — January 8, 2009 @ 9:25 am | Reply

  2. […] previously blogged about this Project Euler puzzle 6 years ago, using ColdFusion.  This is my approach using PHP as a simple practical exercise for myself, and […]

    Pingback by Project Euler: problem 5 (PHP) | Duncan's blog — September 23, 2014 @ 8:09 am | Reply


RSS feed for comments on this post. TrackBack URI

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Blog at WordPress.com.

%d bloggers like this: