Tổng số ≤ N chia hết cho 2 hoặc 5 trong C

Tìm tổng các số tự nhiên ≤ N chia hết cho 2 hoặc 5. Sử dụng nguyên lý bao hàm - loại trừ:

Sum = Sum₂ + Sum₅ - Sum₁₀

Công thức tổng cấp số cộng:

• Sum₂ = (N/2) × (4 + (N/2 - 1)×2) / 2
• Sum₅ = (N/5) × (10 + (N/5 - 1)×5) / 2
• Sum₁₀ = (N/10) × (20 + (N/10 - 1)×10) / 2

Phương pháp này O(1) hiệu quả hơn vòng lặp O(N).

Chương trình

#include <stdio.h>

int main() {
    int n = 25;
    long sum2, sum5, sum10;
    
    sum2 = ((n / 2) * (4 + (n / 2 - 1) * 2)) / 2;
    sum5 = ((n / 5) * (10 + (n / 5 - 1) * 5)) / 2;
    sum10 = ((n / 10) * (20 + (n / 10 - 1) * 10)) / 2;
    
    long sum = sum2 + sum5 - sum10;
    printf("Sum = %ld", sum);
    return 0;
}

Kết quả

Sum = 201