https://hack.codingblocks.com/contests/c/126/821
I’m getting run-error for one test case.
My logic- if N>20, Find no of primes between 21 and N and print(N-(primes)-1) else if N<=20 print(N-1).
I have stored primes from 1 to 10^8 in arr using the prime sieve. But in constraints, its mentioned that the range of N is 10^18. How to find primes beyond that? Do I have to use Segmented Sieve?
Or, is there a better approach.
use Inclusion exclusion principle for this .
Please explain. can’t find any video on it in my course and gfg article is complex to understand.
Hi,
This question is based on inclusion exclusion principle (Set theory)
let a,b,c,d,e,f… represent set of prime numbers less than 20.
Now you have to find
a union b union c union d…
this can be found by inclusion exclusion principle.
In case you need explanation do post it.
Hit like if you get it
Hi
Check out this video, post if you still have doubts
Hit like if you get it. 