Project Euler

Bài toán đầu tiên của Project Euler có nội dung như sau:

Các số tự nhiên nhỏ hơn 10 là bội số của 3 hoặc 5 là 3, 5, 6, 9. Tổng của chúng là 23.Tìm tổng tất cả các số tự nhiên chia hết cho 3 hoặc 5 nhỏ hơn 1000.

Mặc dù bài toán này khá đơn giản, có nhiều cách giải khác nhau.

Cách thứ nhất là liệt kê từng phần tử và kiểm tra xem nó có phải bội số của 3 hoặc 5 hay không.

Cách thứ hai sử dụng tính chất bao hàm - loại trừ. Gọi ${\displaystyle sum_{k}(n)}$ là tổng tất cả các số nhỏ hơn n và là bội số của k. Tổng các số nhỏ hơn n và là bội của 3 hoặc 5 thỏa mãn

${\displaystyle {\begin{aligned}\mathrm {sum} _{\text{3 or 5}}(n)&=\mathrm {sum} _{3}(n)+\mathrm {sum} _{5}(n)-\mathrm {sum} _{15}(n)\\\mathrm {sum} _{k}(n)&=\sum _{i=1}^{\left\lfloor {\frac {n-1}{k}}\right\rfloor }ki\\\sum _{i=1}^{p}ki&=k{\frac {p(p+1)}{2}}\end{aligned}}}$

Đáp số là ${\displaystyle sum_{3or5}(1000)}$

• Website chính thức
• Project Euler Translations - Project Euler Forum