tbquan08hanoi's blog

Prime count in large range
By tbquan08hanoi, history, 4 hours ago, In English

Hello codeforces!

I have a problem: counting primes in $$$[m, n)$$$ where $$$1<=m<n<=2 \cdot 10^9$$$.

Because the range could be large, I can't use sieve because of the memory complexity or normal primality test in $$$O(sqrt(n))$$$

Thanks very much!

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
3 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

Check again your problem, may be you can sieve on range?

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

We call P(i) = the number of primes <= i

The answer for the problem is P(N - 1) - P(M - 1)

since N <= 2 * 10^9, we can preprocess 2000 integers where the i-th one shows P(i * 10^6)

The leftover length is not bigger than 10^6 so you can sieve on that range, it should pass the time limit.

→ Reply
»
103 minutes ago, # |
  Vote: I like it 0 Vote: I do not like it

https://mirror.codeforces.com/blog/entry/91632 Certainly covers your problem

→ Reply