Đếm bội số của 3 hoặc 7 đến N trong C++

Cho N, đếm số nguyên từ 1 đến N chia hết cho 3 hoặc 7.

Ví dụ

N=100 → 43 số (bội của 3 hoặc 7)

Thuật toán

• Duyệt từ 3 đến N, đếm nếu i%3==0 || i%7==0.
• Hoặc dùng nguyên lý bao hàm - loại trừ: N/3 + N/7 - N/21 (O(1)).

Triển khai C++ (cách O(N))

#include <bits/stdc++.h>
using namespace std;

int getMultiplesCount(int n) {
    int count = 0;
    for (int i = 3; i <= n; i++)
        if (i % 3 == 0 || i % 7 == 0) count++;
    return count;
}

int main() {
    cout << getMultiplesCount(100) << endl; // 43
    return 0;
}

Triển khai O(1) tối ưu

int getMultiplesCountFast(int n) {
    return n/3 + n/7 - n/21;
}

Kết quả

43