Đếm số chia hết cho tất cả số từ 2 đến 10 trong C++

Giới thiệu

Cho số n, đếm số nguyên trong [1, n] chia hết cho tất cả các số từ 2 đến 10.

Quan sát quan trọng

Số chia hết cho 2..10 ⇔ chia hết cho BCNN(2,3,4,5,6,7,8,9,10) = 2520.

Kết quả = n / 2520 (chia nguyên).

Ví dụ

n = 10000 → 10000/2520 = 3 (2520, 5040, 7560)
n = 20000 → 20000/2520 = 7

Các cách tiếp cận

Cách 1: Naive O(n × 9)

Kiểm tra từng số 1..n chia hết cho 9 số.

Cách 2: Toán học O(1)

Trả về n / 2520.

Ví dụ triển khai (C++)

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

// Cách 1: Naive
int countDivisible2to10Naive(int n) {
    int count = 0;
    for (int i = 1; i <= n; i++) {
        bool ok = true;
        for (int d = 2; d <= 10; d++)
            if (i % d != 0) { ok = false; break; }
        if (ok) count++;
    }
    return count;
}

// Cách 2: Công thức toán học
int countDivisible2to10Fast(int n) {
    return n / 2520; // BCNN(2..10) = 2520
}

int main() {
    int n = 10000;
    cout << "Naive: " << countDivisible2to10Naive(n) << endl; // 3
    cout << "Fast: " << countDivisible2to10Fast(n) << endl;  // 3
    return 0;
}