Klasycznie rzecz biorąc, to mógłbyś... Na przykład, obliczyć sobie liczby pierwsze Eratostenesem do sqrt(max), potem od sqrt(max) liczyć ręcznie, sprawdzając czy każda z kolei nieparzysta liczba i (poza podzielnymi przez 5) aż do max jest podzielna przez liczby pierwsze mniejsze lub równe sqrt(i).
Ale... O ile ta pierwsza część potrwa dość krótko, to ta druga będzie się nieźle ciągnęła. ;)
U mnie Eratostenes dla 100 000 000 (samo zrobienie sita, bez żadnego io) trwa ok. 1.27s, ale powyższa metoda jest już dużo, dużo wolniejsza, ok 100x używając w sicie wektora bool, a w drugiej fazie wektora unsigned long long (w pewnym momencie używa się wiec całkiem sporo pamięci...) - mała modyfikacja i robi się 3x wolniejsze od poprzedniej (używając tylko wektora bool) - ale przynajmniej ciągle to samo zużycie pamięci. ;)
Tak czy owak sprawdzenie do 10^18 bez zapisu potrwa... Długo.
Całość Eratostenesem:
$ ./bigprimes.exe 1000000000 -erato-pure
Took: 15.718s
i około 130mb zajętej pamięci. Pamięciowo się więc wyrobisz, ale czas... Fiu fiu. Z zapisem do pliku to już w ogóle. ;)
[quote]Branie każdej liczby i sprawdzanie, czy nie jest pierwsza jest zbyt wolne.[/quote]Przy małych przedziałach sporych liczbach to ta metoda może nie być zła, ale... może szybciej będzie jednak sprawdzać czy nie są pierwszymi. Pewnie zależy.