Hello codeforces!
I have a problem: counting primes in $$$[m, n)$$$ where $$$1 \lt =m \lt n \lt =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!
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | Benq | 3792 |
| 2 | VivaciousAubergine | 3647 |
| 3 | jiangly | 3631 |
| 4 | Kevin114514 | 3574 |
| 5 | maroonrk | 3521 |
| 6 | strapple | 3515 |
| 7 | Radewoosh | 3461 |
| 8 | tourist | 3428 |
| 9 | turmax | 3378 |
| 10 | Um_nik | 3376 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | Qingyu | 162 |
| 2 | adamant | 148 |
| 3 | Um_nik | 146 |
| 4 | Dominater069 | 143 |
| 5 | errorgorn | 140 |
| 6 | cry | 138 |
| 7 | Proof_by_QED | 136 |
| 8 | YuukiS | 135 |
| 9 | chromate00 | 134 |
| 10 | soullless | 133 |
Check again your problem, may be you can sieve on range?
We call
P(i) = the number of primes <= iThe 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.
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?
You can find some implementations for sieve on range on the Internet, I would recommend cp-algorithms.
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
what I meant "preprocessing" here is making an array of 2000 integers containing the answer when you run your program in the background.
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
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 ?
I still don't understand how that would not be TLE, if you're talking about parallel programming, I dont know that either ;-;
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
Can you explain , how 2000 integers will cover 10^9-10^6 numbers?
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)$$$
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?
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)$$$.https://mirror.codeforces.com/blog/entry/91632 Certainly covers your problem
Thanks very much, it really helps me a lot