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,
-
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. -
sposob
Wczytuje zakres i dla kazdego zakresu obliczm liczby pierwsze. No i Od razu je wypisuje.
Teraz problemy:
-
metoda
dla zakresu 1 - 107 program po wpisaniu zakresu nic nie robi (zawiesza sie), a dla 1 - 106 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 -
metoda
biorac pod uwage, że <a,b> a=1 b=109 to b-a<=105 (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 ?