Đếm số không chia hết cho bất kỳ số nào trong [2, 10] bằng C++

Cho num, đếm số nguyên từ 1 đến num không chia hết cho bất kỳ số nào trong đoạn [2, 10]. Ví dụ:

Input: 14 → 3 (1, 11, 13) Input: 21 → 5 (1, 11, 13, 17, 19)

Cách hiệu quả: Nguyên lý bao hàm - loại trừ (Inclusion-Exclusion)

Số chia hết bởi ít nhất một trong {2,3,5,7} (vì 4,6,8,10 chia hết 2; 9 chia hết 3). Áp dụng công thức:

Kết quả = n - n/2 - n/3 - n/5 - n/7 + n/6 + n/10 + n/14 + n/15 + n/21 + n/35 - n/30 - n/42 - n/70 - n/105 + n/210

Ví dụ

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

int main() {
    int n = 21, result;
    result = n - n/2 - n/3 - n/5 - n/7
           + n/6 + n/10 + n/14 + n/15 + n/21 + n/35
           - n/30 - n/42 - n/70 - n/105 + n/210;
    cout << "The count of numbers, not div by [2, 10] is: " << result;
    return 0;
}

Kết quả

The count of numbers, not div by [2, 10] is: 5

Kết luận

Đếm số không chia hết cho 2..10 bằng nguyên lý bao hàm - loại trừ O(1). Code C++ ngắn gọn.