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

                //idea to start with the small numbers first because

                //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.  🙂

If you have questions, leave a comment or please find me on Twitter (@azzlsoft) or email (rich@azzlsoft.com).

Problem 4

A palindromic number reads the same both ways. The largest palindrome made from the product of two 2-digit numbers is 9009 = 91 99.

Find the largest palindrome made from the product of two 3-digit numbers.

Solution

using System.Collections.Generic;

//A palindromic number reads the same both ways.

//The largest palindrome made from the product of

//two 2-digit numbers is 9009 = 91  99.

//Find the largest palindrome made from the

//product of two 3-digit numbers.

namespace ProjectEulerCSharp_004

{

    class Program

    {

        static void Main(string[] args)

        {

            //simple placeholder for our

            //biggest palindrome

            int maxPalindrome = 0;

            //loop through each 3-digit number

            for (int i = 100; i < 1000; i++)

            {

                //this is a slight optimization

                //over our F# solution because

                // 100 * 101 = 101 * 100 so we

                // don’t need to perform the second

                // multiplication

                for (int j = i; j < 1000; j++)

                {

                    int product = i * j;

                    //used an extension method to test for

                    //palindromicity (is that a word)

                    if (product.IsPalindrome()

                        && product > maxPalindrome)

                    {

                        maxPalindrome = product;

                    }

                }  

            }

            System.Console.WriteLine(maxPalindrome);

        }

    }

    // extension methods are awesome

    public static class Extensions

    {

        // here we create a function called

        // IsPalindrome that uses the same

        // technique as the F# function

        public static bool IsPalindrome(this int i)

        {

            // get a convenient list of chars

            List<char> chars =

                new List<char>(i.ToString().ToCharArray());

            // reverse them

            chars.Reverse();

            // are we a palindrome?

            return i == int.Parse(new string(chars.ToArray()));

        }

    }

}

Discussion

My favorite part of this solution is the use of the extension method.  Why don’t we use those all the time?  Of course, the generic List structure offers some helpful routines as well.

If you have questions, leave a comment or please find me on Twitter (@azzlsoft) or email (rich@azzlsoft.com).