Zagadka Liczb Pierwszych

Witam. Przy ostatnim projekcie zastanawiałem się jak przy pomocy algorytmu wyszukiwać liczby pierwsze. Przy Sicie Erastotelesa potrzeba jednak dużo pamięci. Mnie jednak interesuje ja można szybciej wyszukiwać liczby pierwsze z konkretnego przedziału.

Np. przedział 100-200 czy wystarczy wyszukiwać tylko liczby nieparzyste których w tym wypadku będzie dokładnie 50?

Chciałbym poznać wasze opinie na ten temat. Jeśli ktoś próbował skonstruować algorytm do wyszukiwania liczb i miał z tym podobny problem?

Przy sicie potrzeba bardzo mało pamięci, dla liczb mniejszych niż 200 - wystarczy: unsigned tb[8]={3};

W sumie racja. Patrząc na to logicznie w danym przedziale potrzeba tylko określonej ilości pamięci na dany przedział. Ale jeśli przedział byłby w granicach 0-5mln? Wtedy trzeba deklarować tyle liczb i szukać... Mi właśnie chodzi o sposoby bez zastosowania sita.. Które liczby należy przeszukać? Wszystkie nieparzyste?

Dla 5 mln - mniej niż 1MB pamięci - wciąż akceptowalne dla współczesnych komputerów.

Pierwiastek z 5 milionów to 2236 + cyfry po przecinku. Pierwszych mniejszych od 2237 jest 331 przygotuj sobie ich tablicę i , jak badana liczba jest niepodzielna przez żadną z nich to z pewnością jest pierwsza. Dodatkowo możesz przyśpieszyć program, jak liczba z tej tablicy jest większa od pierwiastka badanej to z pewnością badana liczba jest pierwsza.

Dla małych liczb (chociażby te Twoje 200) wszystko możesz zrobić najprostszym algorytmem. Tak czy siak czas będzie blisko zeru. Dla liczb większych zrób sito - jak słusznie zauważył @_13th_Dragon to wcale nie zajmie dużo pamięci. Natomiast jeśli jesteś zainteresowany wyszukiwaniem liczb pierwszych w naprawdę dużych przdziałach (rzędu 2^2000) to musisz użyć czegoś wykwintniejszego. Jeśli chcesz, to opiszę najbardziej optymalny algorytm.

Progdeex napisał(a):

W sumie racja. Patrząc na to logicznie w danym przedziale potrzeba tylko określonej ilości pamięci na dany przedział. Ale jeśli przedział byłby w granicach 0-5mln? Wtedy trzeba deklarować tyle liczb i szukać... Mi właśnie chodzi o sposoby bez zastosowania sita.. Które liczby należy przeszukać? Wszystkie nieparzyste?

https://en.wikipedia.org/wiki/Formula_for_primes

Jeden z najbardziej znanych wzorów to Mersenne (z = 2^p - 1), ale taką liczbę trzeba jeszcze zweryfikować.
Obiecujący jest też wzór rekurencyjny podany na ww stronie.

pingwindyktator napisał(a):

Dla małych liczb (chociażby te Twoje 200) wszystko możesz zrobić najprostszym algorytmem. Tak czy siak czas będzie blisko zeru. Dla liczb większych zrób sito - jak słusznie zauważył @_13th_Dragon to wcale nie zajmie dużo pamięci. Natomiast jeśli jesteś zainteresowany wyszukiwaniem liczb pierwszych w naprawdę dużych przdziałach (rzędu 2^2000) to musisz użyć czegoś wykwintniejszego. Jeśli chcesz, to opiszę najbardziej optymalny algorytm.

Opisz ten algorytm :)

Ja miałem taki pomysł by sprawdzać wszystkie liczby nieparzyste oprócz liczb zakończonych cyfrą 5 np. 25, 255, 1005
Czyli np. 11,13,17,19 51,53,57,59 W przedziale 100-200 jest ich 40.. Pytanie czy da się jeszcze bardziej skrócić wyszukiwanie? :)

Zauważ, że

1. wywalasz liczby parzyste - te podzielne przez 2, bo nie ma sensu w nich szukać
2. wywalasz liczby podzielne przez 5, bo nie ma sensu w nich szukać

Dokładnie tak działa sito erastotenesa, tylko to wywala dużo więcej liczb (skreśla z tablicy te podzielne przez 2, później te podzielne przez 3, przez 5, ...). Ty robisz jakąś część tego. Poza tym - nie wymyślaj cudów jeśli mówimy o przedziale 100-200. Zaklep sobie najprostszy algorytm i zmierz czas. Przekonasz się, że i tak będzie bliski zeru, tak jak pisałem.

100-200 to przedział umowny :) Przy bardzo dużych przedziałach ilość sprawdzanych liczb też będzie wielka a czas śmiertelnie długi.. Chodzi o to by go skrócić jak najlepiej. Sprawdzanie kolejno samych liczb nieparzystych to chyba nie najlepszy pomysł. Jest ich ort! wiele :D

Zauważ, że

1. wywalasz liczby parzyste - te podzielne przez 2, bo nie ma sensu w nich szukać
2. wywalasz liczby podzielne przez 5, bo nie ma sensu w nich szukać

A to chyba żart jest? Zastanów się ile czasu zajmie samo przepisywanie tablicy z liczbami. Skąd weźmiesz dzielniki, których będziesz używać do usuwania elementów z tablicy? Czas na znalezienie liczb do usunięcia będzie porównywalny ze... sprawdzeniem, czy są pierwsze! To takie odwrotne sito Eratostenesa napędzane chomikiem-astmatykiem. Jak chcesz sprawdzić w ten sposób pierwszość liczb aż do okolicy 2^32? Będziesz alokował 8GB ciągłego miejsca w pamięci? :-)

Dla małych liczb, powiedzmy do 32b, szukanie sitem Eratostenesa jest względnie szybkie, bo w sicie znajdzie się mało liczb pierwszych (pewnie kilka tysięcy). Dla liczb dużych i bardzo dużych (np.1024b, używane w RSA) stosuje się inny sposób sprawdzania - probabilistyczny. Istnieje kilka testów, jeden z nich (test pierwszości Solovaya-Strassena - https://pl.wikipedia.org/wiki/Test_pierwszo%C5%9Bci_Solovaya-Strassena) kiedyś implementowałem, nie jest jakoś specjalnie skomplikowany. Test ten z prawdopodobieństwem 1/2 stwierdza, czy liczba jest pierwsza (tzn. czy udało się znaleźć tzw. świadka złożoności); jeśli powtórzysz ten test n razy i za każdym razem odpowie, że liczba jest pierwsza, to masz pewność na 1 - 2^n, że liczba faktycznie jest pierwsza.
Inny test probabilistyczny (Millera-Rabina - https://pl.wikipedia.org/wiki/Test_Millera-Rabina) daje pewność pierwszości liczby na poziomie 3/4, czyli po n próbach masz prawdopodobieństwo pomyłki 2^(-2*n).
Czytałem też, że istnieją testy deterministyczne o charakterystyce zbliżonej do logarytmicznej (np. (logn)^12), np. AKS (https://pl.wikipedia.org/wiki/Test_pierwszo%C5%9Bci_AKS), jednak dla bardzo dużych liczb są one wolniejsze od testów probabilistycznych.

Do poczytania:
https://en.wikipedia.org/wiki/Fermat%27s_little_theorem
https://en.wikipedia.org/wiki/Miller%E2%80%93Rabin_primality_test

Tych dwóch testów używa się chociażby w kryptografii, gdzie musimy szybko wyszukiwać duże liczby pierwszy. RSA chociażby - generując klucz wielkości 4k bitów, musimy znaleźć dwie liczby pierwsze rzędu 2^2048. I tak wygenerowanie takiej liczby pierwszej zajęło mi przed chwilą 6 sekund.

Możesz podać dokładnie jak duża jest to liczba?

Nooo... 2^2048, czyli 256 bajtów. Np.

2519590847565789349402718324004839857142928212620403202777713783604366202070
7595556264018525880784406918290641249515082189298559149176184502808489120072
8449926873928072877767359714183472702618963750149718246911650776133798590957
0009733045974880842840179742910064245869181719511874612151517265463228221686
9987549182422433637259085141865462043576798423387184774447920739934236584823
8242811981638150106748104516603773060562016196762561338441436038339044149526
3443219011465754445417842402092461651572335077870774981712577246796292638635
6373289912154831438167899885040445364023527381951378636564391212010397122822
120720357

Vide https://en.wikipedia.org/wiki/RSA_numbers.

Powiedziałem. Rzędu 2^4048. Konkretnie:

15314086968202694808665432139000061788607831703614123892164863763390544164765121028735914368356790776698275910977498241347530870047691272542886847987004337168587033913952464168898916382480652218865199047230449339694863998672532228651586011583069171169048292507900645837057487436481410531723122528372099985452971046306016479327830004130309625943033801489491619127112582989027078017073025161672103462172507822569017466064998005281338355592652745881446247542837112493674727765121495622480188166529070802441612256148565514293488350892654135570076206960169288138374374277292128602338957577297847433424153828757762190537621

Wygenerowanie tego zajęło 3,5 sekundy.

Powyższe linki nie w pełni rozumiem. Ale wychodzi na to ,że wielką liczbę da się szybko obliczyć jeśli ten algorytm,który zastosowałeś jest 100% skuteczny?? Pytam się ,bo nie wiem czy ta liczba to tylko taki 'strzał' programu czy rzeczywista liczba pierwsza.

Algorytmy wykorzystywane do sprawdzania tak dużych liczb to algorytmy probabilistyczne. To znaczy, że określają z pewnym prawdopodobieństwem, że liczba jest pierwsza. Algorytm, który ja zastosowałem myli się raz na 340282366920938463463374607431768211456 prób. Gdybyś chciał mieć 100% pewności, musiałbyś użyć algorytmu deterministycznego, najszybszy z nich to
https://pl.wikipedia.org/wiki/Test_pierwszo%C5%9Bci_AKS
Natomiast działa nieporównywalnie wolniej niż algorytmy probabilistyczne.

AKS.. no tak czemu jeszcze tego nie sprawdziłem.. Można gdzieś znaleźć testy ile czasu potrzeba na obliczenie konkretnej liczby pierwszej? np. liczba 3*10^1000000000000000 przy użyciu AKS i osobno dla zwykłego algorytmu,który tylko dzieli kolejne liczby nieparzyste sprawdzając pierwszość na tak zwany "brutal force"..

Ja Ci powiem. Nigdy nie znajdziesz takiej liczby przy dostępnych technologiach. Żadnym algorytmem.

okej sorry zagalopowałem się za bardzo. Chodzi o porównanie czasu w szukaniu/generowaniu liczby między AKS a prostym dzieleniem..

Ogóle podsumowanie:

1. Liczba Pierwsza dzieli się przez 1 i samą siebie.
2. Liczba pierwsza jest liczbą nieparzystą zakończoną cyframi 1,3,7 lub 9.
3. Przy szukaniu Liczby Pierwszej bierzemy pod uwagę wszystkie liczby nieparzyste oprócz tych z końcówką 5.
4. Tutaj najważniejsze: Istnieje wspólny związek między daną liczbą a sumą jej cyfr dzięki czemu nie musimy sprawdzać każdej liczby nieparzystej tylko te,które trzeba sprawdzić.

Po zebraniu tych punktów w całość można stworzyć całkiem szybkie sito zawierające tylko najpotrzebniejsze liczby do sprawdzania :)

4. Tutaj najważniejsze: Istnieje wspólny związek między daną liczbą a sumą jej cyfr dzięki czemu nie musimy sprawdzać każdej liczby nieparzystej tylko te,które trzeba sprawdzić.
Proszę?

Progdeex napisał(a):

1. Liczba Pierwsza dzieli się przez 1 i samą siebie.
2. Liczba pierwsza jest liczbą nieparzystą zakończoną cyframi 1,3,7 lub 9.
3. Przy szukaniu Liczby Pierwszej bierzemy pod uwagę wszystkie liczby nieparzyste oprócz tych z końcówką 5.
4. Tutaj najważniejsze: Istnieje wspólny związek między daną liczbą a sumą jej cyfr dzięki czemu nie musimy sprawdzać każdej liczby nieparzystej tylko te,które trzeba sprawdzić.

O, zobacz, 9 to liczba pierwsza - zgodne z punktem 1 (nieparzysta i dzieli się przez 1 i samą siebie), 2 (kończy się cyfrą 9), 3 (nie kończy się cyfrą 5) i 4 (istnieje związek między tą liczbą a sumą jej cyfr, więc trzeba sprawdzić tę liczbę tylko jeśli trzeba ją sprawdzić).
Z kolei liczba 5 nie jest liczbą pierwszą, bo kończy się na 5... Wait... What?

A teraz na serio: złożoność obliczeniową sita Eratostenesa możesz znaleźć w sieci, ale ułatwię Ci: O(n * log(n) * log(log(n))). Złożoność obliczeniowa AKS to O(log¹²(n)).
Teraz znajdź takie n, dla którego log¹¹(n) = n * log(log(n)), będziesz miał graniczną wartość, dla złożoność jest podobna.
W praktyce da Ci to tylko orientacyjną wartość, bo złożoność obliczeniowa pokazuje tylko przyrost obliczeń, nie pokazując ile kosztuje ich jednostka. A więc może się okazać, że konkretna implementacja sita będzie sto razy tańsza od konkretnej implementacji AKS, przez co pomylisz się o np. rząd wielkości. Albo cztery.

Ale najpierw proponuję, żebyś zobaczył, co to jest to AKS, bo jak nie kumasz metod probabilistycznych, to krzywe eliptyczne mogą okazać się jeszcze trudniejsze.

@ŁF algorytmy klasy AKS na przestrzeni lat były ulepszane i tak najlepszy z nich ma teraz złożoność O(log2(n) ^ 7.5). Natomiast dalej jest to cholernie dużo dla tej klasy problemu.
@Progdeex, chciałeś porównania, proszę bardzo. Weźmy liczbę 2**2048 i sprawdźmy czy jest pierwsza.

Brute force - 89884656743115795386465259539451236680898848947115328636715040578866337902750481566354238661203768010560056939935696678829394884407208311246423715319737062188883946712432742638151109800623047059726541476042502884419075341171231440736956555270413618581675255342293149119973622969239858152417678164812112068608 operacji

AKS - ~6800000000000000000000000 operacji

Miller-Rabin x64 - 549755813888 operacji

Sam sobie odpowiedz na pytanie czy AKS podoła tak dużym liczbom.
Disclaimer: obliczenia są bardzo mniej więcej

Pytasz się jak długo zajmie sprawdzanie czy liczba rzędu 3*10^1000000000000000 jest liczbą pierwszą. Wygugluj largest known prime i zobacz ** jak bardzo ** Twoja liczba jest większa od największej znanej. Nie rozumiesz chyba trudności problemu. Mój algorytm właśnie wygenerował liczbę rzędu 2^8000 i zajęło mu to 22 minuty.

ŁF napisał(a):

O, zobacz, 9 to liczba pierwsza - zgodne z punktem 1 (nieparzysta i dzieli się przez 1 i samą siebie), 2 (kończy się cyfrą 9), 3 (nie kończy się cyfrą 5) i 4 (istnieje związek między tą liczbą a sumą jej cyfr, więc trzeba sprawdzić tę liczbę tylko jeśli trzeba ją sprawdzić).
Z kolei liczba 5 nie jest liczbą pierwszą, bo kończy się na 5... Wait... What?

Dla samych cyfr/liczb jednocyfrowych się to nie tyczy ,bo jest ich zaledwie 4.. Do całej reszty powinno pasować. POWINNO, bo nie sprawdzi się całej nieskończoności.

Eh... żeby sprawdzić, że liczba kończy się piątką, to i tak musisz podzielić przez pięć, chyba, że masz w planach zbudować tablicę wszystkich liczb, ale tu szybko ograniczy Cię rozmiar pamięci (16GB pamięci nie gwarantuje, że znajdzie się ciągły blok choćby i na 1GB).
Odkrywasz koło na nowo. Tęgie umysły zjadły na tym zęby, a Ty uważasz, że tu sobie odsiejesz, tam odfiltrujesz i będziesz mieć szybko duże pierwsze liczby. Zacznij implementować i w ten sposób weryfikować swoje pomysły. Nota bene - moim zdaniem - słabe, bo brakuje Ci tony wiedzy.

Od siebie dodam literaturę: Henry S. Warren, "Uczta programistów"; rozdział 16 strona 299.
Jest tam opisane kilka ciekawych przykładów.

ŁF napisał(a):

Eh... żeby sprawdzić, że liczba kończy się piątką, to i tak musisz podzielić przez pięć, chyba, że masz w planach zbudować tablicę wszystkich liczb, ale tu szybko ograniczy Cię rozmiar pamięci (16GB pamięci nie gwarantuje, że znajdzie się ciągły blok choćby i na 1GB).

Nie trzeba sprawdzać czy liczba kończy się piątką,bo zwyczajnie nie będzie tej liczby w zbiorze liczb, które są sprawdzane. Tak jak już pisałem w danym przedziale np. Umownym 100-200 sprawdzimy tylko 28 liczb. Reszty nie trzeba

LOL. A jak sprawdzisz, czy liczba kończy się piątką bez dzielenia przez 5? Oznaczając odpowiednie indeksy w tabelce? To rozwiązanie czysto akademickie; użyj tej metody do sprawdzenia liczby 2³² - 3.

Czy istnieją już jakieś algorytmy oparte o hipotezę Riemanna ?

ŁF napisał(a):

LOL. A jak sprawdzisz, czy liczba kończy się piątką bez dzielenia przez 5? Oznaczając odpowiednie indeksy w tabelce? To rozwiązanie czysto akademickie; użyj tej metody do sprawdzenia liczby 2³² - 3.

Chodzi Ci o to ,by taką liczbę sprawdzić znając tylko podstawę oraz jej potęgę? Ja piszę trochę o innej metodzie: Szukanie liczb poprzez generowanie kolejnych liczb nieparzystych dzielonych przez poprzednie liczby pierwsze. Chodzi o to by generować liczby,których prawdopodobieństwo bycia L.Pierwszą jest wysokie, a dopiero potem taką liczbę sprawdzić. Dlatego pisałem,że liczb z końcówką 5 nie trzeba sprawdzać,bo nie będą powstawać.