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

Tính tổng của các số tự nhiên chia hết cho 3 hoặc 5 nhưng nhỏ hơn 1000.

Phân tích

Tổng của tất cả các số tự nhiên liên tiếp từ 1 tới x là : x(x+1)/2  gọi tổng này là sum

Sẽ có floor(x/3) số giữa 1 và x sẽ chia hết cho 3 (floor trả lại số nguyên lớn nhất không lớn hơn x/3) (giả sử kết quả là số nguyên.

Ví dụ từ 1 tới 10 thì có floor(10/3)=3 số là 3,6,9 tổng 3+6+9 =18

Như vậy có thể viết lại

3+6+9 = 3/3 * (3+6+9) = 3* (1+2+3)

Như vậy tổng các số chia hết cho 3 nhỏ hơn x bằng 3* sum (x/3)

Tương tự tổng các số chia hết cho 5 nhỏ hơn x bằng 5 * sum (x/5)

Tuy nhiên tổng này vẫn tính kèm cả số chia hết cho cả 3 và 5, nếu tính tổng thì sẽ bị lặp

Như vậy cần trừ đi tổng các số chia hết cho cả 3 và 5 tức là 15* sum (x/15)

#include <iostream> // hàm tính tổng số liên tiếp unsigned long long sum(unsigned long long x) { return x * (x + 1) / 2; } int main() { unsigned int tests; tests = 1; while (tests--) { unsigned long long last; last = 1000;     //Bỏ số 1000 đi last--; auto sumThree = 3 * sum(last / 3); auto sumFive = 5 * sum(last / 5); auto sumFifteen = 15 * sum(last / 15); std::cout << (sumThree + sumFive - sumFifteen) << std::endl; } return 0; }