Problem Link : Here
How to approach this problem?
I got the logic to solve as:
- The no.s in the range >60 and <=n(given) which are not special(See the problem statement) has to be prime.
- So the ans would be like n — (count of primes in range [61,n])
- Would seive work Here?(as constraints are high)
I came to know about the prime no. theorem which gives the approx count of prime no.s less than x [as pi(x) = x/ln(x) or pi(x) = x/(ln(x)-1)]
Every bit of help would be appreciated :)
Thank you so much! for giving a look to this blog.
What you are saying is not a solution.
Here is an idea:
Until 60 there are only 17 prime numbers. Let’s say that $$$A_p$$$ is the set of multiples of the $$$p$$$-th prime number in the range $$$1\dots N$$$. Then, what you want is $$$N - |A_1 \cup A_2 \cup A_3 \cup \dots \cup A_{17}|$$$.
$$$ |A_1 \cup A_2 \cup A_3 \cup \dots \cup A_{17}|$$$ can be computed easily with Inclusion-Exclusion Principle.
Okay! got to learn new thing (inclusion-exclusion principle) Thanks!
Here is a link to a similar problem on the CSES (Mathematics) Problem Set: Prime Multiples