Wygenerowanie liczb pierwszych do 10^12

Cześć!

W jaki sposób najlepiej wygenerować i przechować miliard i więcej liczb pierwszych w możliwie najkrótszym czasie (do jednego dnia)? Sito jest podobno najszybsze, jednak pod względem dostępnej pamięci nie jest to najlepszy pomysł. Programuję w C++, więc rozmiar tablicy jest ograniczony. Ma ktoś jakiś pomysł?

Dla sita Eratostenesa możesz dzielić odpowiednio przedziały. Moim zdaniem (mogą być lepsze sposoby) robisz tak:

1. Generujesz liczby pierwsze do sqrt(10^9) => do 31622.
2. Dzielisz przedział <1, 10^9> na mniejsze przedziały, np. po 10 milionów (taka struktura zajmie wtedy mniej niż 39MB).
3. Robisz sito na każdym kolejnym przedziale, ale używając liczb pierwszych wygenerowanych w (1).

Czy to uda się zrobić w dzień? Nie mam pojęcia.

powiedzmy, że korzystamy z sita. zakładając, że na każdą liczbę w siecie przeznaczamy 1 bit (nie bajt) potrzebujemy 116 GB pamięci. jeśli dysponujesz odpowiednio dużym dyskiem twardym, da się to zrobić ;)

ale oczywiście pewnie jest jakiś lepszy sposób.

@mnbvcX - sito polega właśnie na tym, że korzysta z poprzednich wyników, twój sposób raczej jest nieprawidłowy.

zaciekawił mnie ten problem. jak wrócę z pracy i nie znajdę niczego lepszego niż zrzucanie sita na dysk, to zrobię i podzielę się wynikami ;)

Kto Ci nagadał takich bzdur że sito Erastotenesa jest najszybsze (może dla danych bardzo małych)? To jest jedna z najwolniejszych metod które znam, chociaż różne wariacji czasami do średnich danych np. do 10^{12 dobrze działają. Do bardzo prostych a wystarczających do znalezienia tylu liczb pierwszych jest sito erastotenesa tylko podzielone na segmenty, pamięciowo zajmuje mniej więcej tyle ile liczb pierwszych potrzebujesz, właśnie sprawdziłem stary mój kod zoptymalizowany na danych do 10}11 liczy wszystkie liczby pierwsze w coś ponad 8 minut. Istnieją, też bardzo proste metody jak sito atkina, ale z tego co pamiętam nie udało mi się chyba nim osiągnąć świetnych wyników, chociaż pamięciowo gdyby dopracować dobrze i zmniejszyć liczbę skoków wydaje się też dobre. Istnieją trochę bardziej skomplikowane metody o którym mogę napisać innym razem, ponieważ nie mam teraz za dużo czasu.

Coś w podobnym guście jak mnbvcX znajduje mi liczby pierwsze do 10^9 w czasie 8 sekund.

Coś mi się wydaje, że wystarczy ci powszechnie stosowane rozwiązanie przybliżone. Poszukaj w google Chiński test pierwszości.

mi sie zdaje ze chodzi tutaj o wypisanie jakiegos wyniku ze np. liczba 3 w tablicy bedzie liczba x

liczba 10000 w tablicy bedzie liczba y
trzebaby bylo jakis wzorek znalezc :P

wtedy nie bedzie w ogole potrzebna tablica teoretycznie

Programuję w C++, więc rozmiar tablicy jest ograniczony
nie rozumiem; to że programujesz w C++ akurat daje najmniejsze ograniczenie ze wszystkiego co mi do głowy przychodzi.

Jeżeli tylko tyle potrzebujesz, to tak jak już pisaliśmy najłatwiej sobie zrobić sito segmentowe, na początku można wziąć tylko liczby nieparzyste i lecieć po kawałkach np. 2^{17 i przesiewać gromadząc jednocześnie liczby pierwsze, które w tym przesiewaniu wykorzystujemy, plus liczby reprezentować jako bity w jakimś incie, longu co łącznie eliminuje duże skoki po tablicy i w porównaniu ze zwykłym sitem jest znacznie lepsze, dla danych 10}10 przy drobnej optymalizacji działa ok. Możesz też zrobić sito w którym wywalisz sobie wielokrotności liczb 2,3,5,7,11,13,17,19,23,29, im więcej tym lepiej, ale bardziej skomplikowany kod, to samo w segmentowym możesz zastosować.

Co do testów pierwszości to autor chyba chce co innego osiągnąć.

btw zastanawiałem się kiedyś jaką metodę zastosować, żeby wygenerować wszystkie liczby pierwsze do liczby 10^{15 albo 10}16, mam kilka podejść, ale nie są super szybkie, może ktoś słyszał o jakieś fajnej metodzie?