Please read the new rule regarding the restriction on the use of AI tools. It applies starting from round 972. ×

tbquan08hanoi's blog

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

»
10 days ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
10 days 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
  • »
    »
    10 days 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
    • »
      »
      »
      10 days 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
  • »
    »
    10 days 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
    • »
      »
      »
      10 days 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
      • »
        »
        »
        »
        9 days 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
        • »
          »
          »
          »
          »
          9 days 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
          • »
            »
            »
            »
            »
            »
            4 days 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
            • »
              »
              »
              »
              »
              »
              »
              4 days 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
  • »
    »
    4 days 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
    • »
      »
      »
      4 days 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
      • »
        »
        »
        »
        4 days 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
        • »
          »
          »
          »
          »
          4 days 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
»
10 days ago, # |
  Vote: I like it +3 Vote: I do not like it

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

→ Reply