Code Snippet - Smallest Number Divisible by 1-20

Code Snippet - Smallest Number Divisible by 1-20

This algorithm will calculate the lowest number that is evenly divisible by all of the numbers from 1-20. This is one of the Project Euler problems (ProjectEuler.net), which i have recently taken to playing with. I really enjoy thinking in a completely different way to my day job, and this is a great place to do that. Check it out below.

The code uses a do-while loop to increase the number to be tested from 1 to as high as is needed to allow the number to be divisable by 20 and all numbers below.

The for loop iterates through each number up to 20, and the if statement checks to see if the remainder is 0 or not. if it is not, then the number being tested cannot be right, so the for loop breaks and the do-while loop iterates again, having incremented the counter..

public static void Divider() //counting up from low to high
{
    int p = 0, i;  
   
    do  
    {          
        p++;
        for(i = 1; i <=20; i++)   
        {   
                if (!(p%i == 0))break;   
        }    
    } while(i<=20);  
  
    System.Console.WriteLine("Result: " + p); 
}

Update:
After a bit of thinking followed by some optimisation and refactoring, the code below is a considerably faster way to compute the result.

The method above takes about 10seconds to complete, depending on your system; the new method, below, takes about 200ms on the systems I have tested it on.

The counter int q jumps up 20 with each iteration as we know that the result has to be divisible by 20. The for loop starts counting backwards, counting from 20-1, but stops at 10, this is because if a number is divisible by the numbers 11-20, it is divisible by the numbers 1-10, so there is no need to test them. Also, counting backwards means that the higher numbers are reached first, and these are the ones that are harder to divide evenly by.

public static void Divider() //counting down from high to low
{
    int q = 0, j;  
  
    do  
    {          
        q+=20; //adds 20 per loop instead of 1, as we know that the result has to be divided by 20 with the remainder of 0
        for(j = 20; j>10; j--)   
        {   
                if (!(q%j == 0))break;   
        }    
    } while(j>10);    

    System.Console.WriteLine("Result: " + q);   
}  

I'll keep looking for further optimisations, I'm sure there are some somewhere...