How to find exact count of prime no.s in a given range ?

Revision en1, by slow_hare, 2021-01-30 17:53:20

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.

Tags #prime numbers, #long long, #first, problem solv

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en2 English slow_hare 2021-01-30 18:07:44 2 Tiny change: 'preciated ;)\n\nThank' -> 'preciated :)\n\nThank'
en1 English slow_hare 2021-01-30 17:53:20 713 Initial revision (published)