Блог пользователя tbquan08hanoi

Prime count in large range
Автор tbquan08hanoi, история, 6 часов назад, По-английски

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!

  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится

»
5 часов назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

→ Ответить
»
5 часов назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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.

→ Ответить
  • »
    »
    102 минуты назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    How to use sieve on range [l,r], where l is very big? Don't we have to know all primes before l to apply sieve?

    → Ответить
»
4 часа назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

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

→ Ответить