Monday, June 27, 2011

Project Euler #5 - Java

Question:
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?

Answer:
I'll admit I had to spend some serious time thinking about the best way to tackle this one. Then, it just sort of came to me. The answer is practically hidden within the question! One important fact is given: 2520 is the smallest number that can be divided by each of the numbers from 1 to 10 without any remainder. What this means is that the number we are looking for MUST be a multiple of 2520! So all we have to do, is check each and every multiple of 2520 to see if the integers 11-20 divide it evenly. If they all divide in, we found the number! 

With that in mind, I believe the code speaks for itself and does not require further explanation. 


public class euler_05 
{
    final static int multiple = 2520;
    
    public static void main(String[] args) 
    {
            
        int smallest = 2520; 
        boolean done = false;     
        
        while (!done)
        {
            for (int i = 11; i <= 20; i++)
            {
                if ( smallest % i > 0 )
                {
                    smallest += multiple; 
                    break;
                }
                
                if ( i == 20 )
                    done = true;
            }
        }
           
        System.out.printf("The smallest multiple divisible by 1-20 is %d\n",  smallest);
    }
}

No comments:

Post a Comment