zadanie:Generowanie liczb pierwszych

A więc mam następujące zadanie od wykonania, mam podane n przedziałów, pomiedzy ktorymi mam szukac liczb pierwszych
Od 1 do 10^9
Program na wykonanie ma limit 6 sekund.

Wymyśliłem 2 metody rozwiazania,

1. metoda
   Wczytuje zakresy (przedzialy), wyznaczam minimalna liczbe i maksymalna liczbe, pomiedzy ktorymi maja byc generowane liczby pierwsze, no a przy wypisywaniu po prostu sprawdzam czy dana liczba pierwsza miesci sie w przedziale.

2. sposob
   Wczytuje zakres i dla kazdego zakresu obliczm liczby pierwsze. No i Od razu je wypisuje.

Teraz problemy:

1. metoda
   dla zakresu 1 - 10^{7 program po wpisaniu zakresu nic nie robi (zawiesza sie), a dla 1 - 10}6 generowane sa liczby. Wiec pojawia się problem w pojemnosci tabeli, gdyż do niej wlasnie wpisuje liczby pierwsze a dopiero pozniej je wypisuje, chodzi o zakres gdyż kompilator g++ przy tabeli z 10^6 komórek powoduje zwrocenie bledu przy kompilacji

2. metoda
   biorac pod uwage, że <a,b> a=1 b=10^{9 to b-a<=10}5 (to jest w tresci zadania). Co by rozwiązywało problem z pojemnoscia tabeli, jednak ten sposób działa znacznie wolniej przy podaniu wielu zakresów.

Jeżeli mam liczbe m to sprawdzam czy dana liczba nie dzieli się przez liczby pierwsze poczawszy od 2 do najlizszej liczby pierwszej nie wiekszej niż pierwiastek z m. To stosuje w obu metodach.

Jakie jest rozwiazanie tego problemu ?

co do drugiej metody - IMO nie przejdzie ;-P
pierwsza wyglada w miare ok ;-) tyle.

Liczby pierwsze sie filtruje a nie generuje - tzw. sito erastotenesa. Zeby zmniejszyc zapotrzebowanie na pamiec mozesz zauwazyc:

• jest tylko 1 liczba pierwsza parzysta (2), wiec o reszcie nie trzeba nic pamietac.

• do pamietania info o tym czy liczba jest pierwsza czy nie wystarczy 1 bit.

Przy tych zalozeniach potrzebujesz tablicy typu char rozmiaru (10^7)/(2*8) = 6,25e5. (Jezeli to malo to mozna latwo jeszcze zredukowac ta liczbe - opis jest w piramidach i szyszkach Sysły).

To taki mój konik, zobacz o czym mówiliśmy np. w:
Liczby pierwsze - szybki algorytm, pytania mile widziane ;-)