"Project Euler is a series of challenging mathematical/computer programming problems that will require more than just mathematical insights to solve. Although mathematics will help you arrive at elegant and efficient methods, the use of a computer and programming skills will be required to solve most problems." - Project Euler .Net
Maths problems aren't something we've been going out of our way to find. In fact we were looking for Code Katas when we found Project Euler. The first Code Kata, Supermarket Pricing, isn't immediately a programming problem. In fact it doesn't take a tremendous leap to flesh out concrete example code even though the real idea is to practise some modelling. So in pursuit of an immediate problem requiring an immediate solution via code:
#1 Add all the natural numbers below one thousand that are multiples of 3 or 5
No, it's not in the least bit difficult but that's not the idea. The obvious solution:
public static long AddNumbersThatAreMultiplesOf(int Min, int Max, int[] Primes)
{
long sum = 0;
for (int i = Min; i < Max; i++)
{
foreach (int p in Primes)
{
if (i % p == 0)
{
sum += i;
break;
}
}
}
return sum;
}
It's an example of doing just enough to get the right answer. A better solution (cleverly translated from PHP) is below:
public static double GetAnswerUsingMoreOptimalSolution()
{
long max = 1000;
double SumOfMultiplesOfThreeBelowMax = 1.5 * (int)((max-1)/3) * (int)((max+2)/3);
double SumOfMultiplesOfFiveBelowMax = 2.5 * (int)((max-1)/5) * (int)((max+4)/5);
double SumOfMultiplesOfFifteenBelowMax = 7.5 * (int)((max-1)/15)*(int)((max+14)/15);
return SumOfMultiplesOfThreeBelowMax + SumOfMultiplesOfFiveBelowMax - SumOfMultiplesOfFifteenBelowMax;
}
This more optimal solution (not mine) looks to be derived from GCSE mathematics, the formula for arithmetic progressions: A sum of terms equals (n/2)(a+l), where n is the number of terms, a is the first term, and l is the last term.
Note: The obvious refactoring in GetAnswerUsingMoreOptimalSolution() has been left intentionally :)
Subscribe