不可分割的数字

Question

你将得到一个正整数N.你的任务是找到正整数K≤N的数量,这样K就不能被集合中的任何数字整除{2,3,4,5,6,7,8,9 ,10}.

我正在考虑所有的素数,但它没有给出正确的答案.

令人惊讶的是,答案非常简单.

#include <iostream>
using namespace std;

int main() {
    int t;
    cin>>t;
    while(t--) {
        long long n;
        cin>>n;
        long long ans = (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<<n - ans<<endl;
    }
    return 0;
}

但我不明白这个算法.任何人都可以解释这个算法.

Answer 1

集合中的素数是2,3,5和7.使用这些,我们计算:

how many numbers up to N are divisible by 2, 3, 5 and 7

但随后我们克服了可被两者整除的数字:

2,3 = 6
2,5 = 10
2,7 = 14
etc.

但后来我们过度减去了所有三个可以整除的数字:

2,3,5 = 30
2,3,7 = 42
etc.

等等...

这种组合原理称为包含 - 排除.

在这个过程之后留下的任何东西都不能被那些素数整除.(注意,如果一个数字不能被2整除,它就不能被4,6,8和10整除; 3和9也是一样的.)