Muszę napisać program obliczający ilość liczb pierwszych w przedziale od a do b, gdzie a,b<=10^9 oraz b-a<=10^6. Otóż nie wiem, jak obliczyć ilość liczb pierwszych w tak dużym przedziale - sitem Eratostenesa nie wyjdzie, bo za duże wartości. Można co prawda skorzystać z własności b-a<=10^6, aczkolwiek nie wiem, w jaki sposób...
0
0
https://en.wikipedia.org/wiki/Prime-counting_function przy czym sito Erastotenesa musiałbyś przepuścić do ~10^5 by mieć wynik ok, a mógłbyś to zrobić w czasie kompilacji, by nie liczyć go znów w czasie wykonania. Ewentualnie możesz też użyć sita Atkina, ale statyczna tablica będzie zdecydowanie szybsza.
0
Ale liczby pierwsze muszę znaleźć do liczby 10^9... Więc znalezienie do 10^5 nic mi nie da