Number that are not divisible

Question

You will be given a positive integer N. Your task is to find the number of positive integers K ≤ N such that K is not divisible by any number among the set {2,3,4,5,6,7,8,9,10}.

I was thinking about all the prime numbers but it is not giving the correct answer.

Surprisingly,answer is very simple.

#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;
}

But I did not understand this algo.Can anyone please explain me this algo.

Answer 1

The primes in the set are 2, 3 ,5 and 7. Using these, we count:

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

but then we overcounted the numbers that are divisible by both:

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

but then we over-subtracted all the numbers divisible by all three of:

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

etc...

This combinatoric principle is called inclusion-exclusion.

Whatever is left after this process was not divisible by those primes. (Note that if a number is not divisible by 2, it's not divisible by 4, 6, 8 and 10; same for 3 and 9.)