Prime count in large range

→ Обратите внимание

До соревнования
CodeTON Round 9 (Div. 1 + Div. 2, Rated, Prizes!)
30:23:24
Зарегистрироваться »

*есть доп. регистрация

→ Лидеры (рейтинг)

№	Пользователь	Рейтинг
1	tourist	4009
2	jiangly	3823
3	Benq	3738
4	Radewoosh	3633
5	jqdai0815	3620
6	orzdevinwang	3529
7	ecnerwala	3446
8	Um_nik	3396
9	ksun48	3390
10	gamegame	3386

Страны | Города | Организации

Всё →

→ Лидеры (вклад)

№	Пользователь	Вклад
1	cry	167
2	Um_nik	163
3	maomao90	162
3	atcoder_official	162
5	adamant	159
6	-is-this-fft-	158
7	awoo	157
8	TheScrasse	154
9	Dominater069	153
9	nor	153

Всё →

→ Найти пользователя

→ Прямой эфир

Детальнее →

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

Prime count in large range

Автор tbquan08hanoi, история, 3 месяца назад, По-английски

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!

primality test, primes, prime

tbquan08hanoi
3 месяца назад
16

Комментарии (16)

Написать комментарий?

ThegodbridgeXD

3 месяца назад, # |

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

→ Ответить

TrendBattles

3 месяца назад, # |

+14

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.

→ Ответить

qwertylkjhg

3 месяца назад, # ^ |

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?

→ Ответить

TrendBattles

3 месяца назад, # ^ |

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

→ Ответить

BhosdiwalaLodu

3 месяца назад, # ^ |

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

→ Ответить

TrendBattles

3 месяца назад, # ^ |

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

→ Ответить

BhosdiwalaLodu

2 месяца назад, # ^ |

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

→ Ответить

TrendBattles

2 месяца назад, # ^ |

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 ?

→ Ответить

BhosdiwalaLodu

2 месяца назад, # ^ |

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

→ Ответить

VitalyKo

2 месяца назад, # ^ |

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

→ Ответить

smit_384

2 месяца назад, # ^ |

← Rev. 2 →

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

→ Ответить

VitalyKo

2 месяца назад, # ^ |

← Rev. 3 →

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)$$$

→ Ответить