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.
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.)
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With