tbquan08hanoi's blog

Prime count in large range
By tbquan08hanoi, history, 2 months 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

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
2 months ago, # |
  Vote: I like it +14 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
  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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?

    → Reply
    • »
      »
      »
      2 months ago, # ^ |
        Vote: I like it +8 Vote: I do not like it

      You can find some implementations for sieve on range on the Internet, I would recommend cp-algorithms.

      → Reply
  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    to preprocess 2000 integers ith one for i*1e6 wouldnt that be 2e9 itself, what do you mean :( '-' ;-;

    explain what you mean, i couldnt understand anything

    → Reply
    • »
      »
      »
      2 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      what I meant "preprocessing" here is making an array of 2000 integers containing the answer when you run your program in the background.

      → Reply
      • »
        »
        »
        »
        2 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        but how come that isnt TLE, I asked chat gpt to code but its code also gave me TLE. Can you share some standard resource for it, Im not able to get it pewpew

        → Reply
        • »
          »
          »
          »
          »
          2 months ago, # ^ |
            Vote: I like it +8 Vote: I do not like it

          calculating those 2000 integers in another program and get the results out in a file, then copy them into the main program

          did I make it clueless ?

          → Reply
          • »
            »
            »
            »
            »
            »
            2 months ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            I still don't understand how that would not be TLE, if you're talking about parallel programming, I dont know that either ;-;

            → Reply
            • »
              »
              »
              »
              »
              »
              »
              2 months ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

              You calculate these 2000 answers on your machine locally.
              It might take some time and after that you just paste them in an array in your solution.
              And you can use them to get the answer by only prime checking less than 10^6 needed numbers

              → Reply
  • »
    »
    2 months ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    Can you explain , how 2000 integers will cover 10^9-10^6 numbers?

    → Reply
    • »
      »
      »
      2 months ago, # ^ |
      ← Rev. 3   Vote: I like it +3 Vote: I do not like it

      For example
      $$$3 * 10^8 {\space}{\le}{\space} l {\space}{\lt}{\space} 3 * 10^8 + 10^6$$$

      Then we take a precalculated value $$$P(3 * 10^8)$$$ and make a loop from $$$3 * 10^8$$$ to $$$l$$$, so we get $$$P(l)$$$ by only checking a small count of numbers.

      Then same for $$$P(r)$$$ and answer is $$$P(r) - P(l)$$$

      → Reply
      • »
        »
        »
        »
        2 months ago, # ^ |
        ← Rev. 2   Vote: I like it 0 Vote: I do not like it

        what do you mean by "make a loop from 3e8 to l" , do we check sqrt(i) test for each i from 3e8 to l?

        → Reply
        • »
          »
          »
          »
          »
          2 months ago, # ^ |
            Vote: I like it +3 Vote: I do not like it

          The complexity of for (int i=2;i*i<=r;++i) for (int j=i*((l+i-1)/i);j<=r;j+=i) prime[j]=false; is $$$O(\sqrt{r}+(r-l)\log r)$$$.

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

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

→ Reply