## Project Euler 005 – C#

1 03 2011

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

Solution

// 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?

namespace ProjectEulerCSharp_005

{

class Program

{

static void Main(string[] args)

{

//have we found the answer yet?

//let’s start off by saying "no"

bool notFound = true;

//20 seems like as good of a

//starting spot as any

long candidate = 20;

while(notFound)

{

//I am incrementing up front

//so that my loop exits elegantly

candidate++;

//here I am assuming that this candidate

//is the answer.  I set it back when I

//find a divisor that it doesn’t work for

notFound = false;

//this is not too important, but it’s a good

//they are more likely to fail

for (int divisor = 2; divisor <= 20; divisor++)

{

if (candidate % divisor != 0)

{

notFound = true;

break;

}

}

}

System.Console.WriteLine(candidate);

}

}

}

Discussion

The brute force approach is pretty silly, but it does work and within the 1 minute rule.  It takes about 7.5 seconds on my 6 month old laptop.  When this problem was announced (November 2001) the same code would have probably taken over 10 minutes to complete – at least according to my back of the napkin estimation of Moore’s law.  🙂