slow_hare's blog

How to find exact count of prime no.s in a given range ?
By slow_hare, history, 4 years ago, In English

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.

  • Vote: I like it
  • +11
  • Vote: I do not like it

Comments Comments (3)
| Write comment?
»
4 years ago, # |
  Vote: I like it +11 Vote: I do not like it

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.

→ Reply
»
4 years ago, # |
  Vote: I like it +8 Vote: I do not like it

Okay! got to learn new thing (inclusion-exclusion principle) Thanks!

→ Reply
»
4 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Here is a link to a similar problem on the CSES (Mathematics) Problem Set: Prime Multiples

→ Reply