Project Euler Problem 1

If we list all the natural numbers below 10 that are multiples of 3 or 5, we get 3, 5, 6 and 9. The sum of these multiples is 23.

Find the sum of all the multiples of 3 or 5 below 1000.

PHP Script

<?php
for($i = 0; $i < 1000; $i++) {
	if($i % 3 == 0 || $i % 5 == 0) {
		$sum += $i;
	}
}
echo $sum;
?>

C Script

#include <stdio.h>

int main (int argc, const char * argv[]) {
	int i = 1;
	int sum = 0;
	while(i < 1000) {
		if(i % 5 == 0 || i % 3 == 0) {
			sum+= i;
		}
		i++;
	}
	printf("%d", sum);
	return 0;
}

Manual Solving

Considering this is a simple problem, it’s also possible to solve by hand.

Between 0 and 1000, there are 333 numbers that are divisible by 3, so we have to first find the sum of those numbers. Knowing that a + a+d + a+2d + a+3d + ... + a+(n - 1)d is equal to n(n + a)/2, where a is the first number, d is the difference between the numbers, and n is the total number of numbers. With that, we can come up with the equation 333(999 + 3) / 2, which gives you 166833.

Now we have to find the 5 + 10 + 15 + … + 995. Here, we will use 199(995 + 5) / 2, which will give us 99500.

Now that we have the sum of all the multiples of 3 and 5, we must add them together. Doing so will give us 266333. However, we must keep in mind there are numbers such as 15 and 30 that are both divisible by 3 and 5. Since 15 is the least common multiple between 3 and 5, we must subtract all the multiples of 15. 66(990 + 15) / 2 gives us 33165.

To find the final answer, do 166833 + 99500 - 33165 and you will get 233168. Here’s a PHP script to explain the “manual” process.

<?php
$a = 333 * (999 + 3) / 2;
$b = 199 * (995 + 5) / 2;
$c = 66 * (990 + 15 ) / 2;

echo $a + $b - $c;
?>

Leave a Reply

Your email address will not be published.