zadanie:Generowanie liczb pierwszych

Odpowiedz Nowy wątek
2006-10-20 16:29

Rejestracja: 16 lat temu

Ostatnio: 4 lata temu

0

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 poprostu sprawdzam czy dana liczba pierwsza miesci sie w przedziale.

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

Teraz problemy:

  1. 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

  2. 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 ?

Pozostało 580 znaków

2006-10-20 18:55

Rejestracja: 14 lat temu

Ostatnio: 8 lat temu

0

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).


Pozostało 580 znaków

2006-10-20 19:08

Rejestracja: 15 lat temu

Ostatnio: 1 miesiąc temu

0

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

Pozostało 580 znaków

Odpowiedz

1 użytkowników online, w tym zalogowanych: 0, gości: 1, botów: 0