A number that is 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 thought about all the prime numbers, but it does not give the correct answer.

Surprisingly, the 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 this algo to me.

Answer 1

Prime numbers in the set 2, 3, 5 and 7. Using them, we consider:

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

but then we listed the numbers that are divided into both:

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

but then we crossed out all the numbers divisible by all three of:

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

etc...

This combinatorial principle is called inclusion-exception .

, , . (, 2, 4, 6, 8 10, 3 9.)

Answer 2

, .

• n/2 2.
• n/3 3.
• .

. , 6, 2 3, .

, 30, ( 2, 3 5), ( 6, 10 15). , 1.

, , , .

Answer 3

There is a non-recursive solution.

int N = ....; 
int const primes[4] = {2,3,5,7};
int result = 0;
for(int i = 0; i < 16; ++i)// 16 = 2^4
{ 
    int p = 1, s = 1; // s = (-1)^bits(i).
    for(int j = 0; j < 4; ++j)
        if ( ( i >> j ) & 1 ) 
            p *= primes[j], s *= -1;

    result += (N / p) * s; 
}