Sposób na znajdowanie liczb pierwszych

arigo · Post autor: **arigo** » 17 gru 2005, o 12:19

1. martnotrawstwo pamieci to sobie narzucliscie sami

po co traic 87,5% pamieci ?
2. (i = 2; i

juzef · Post autor: **juzef** » 17 gru 2005, o 13:21

Ten program był pisany przez jakieś 5 minut. Po co optymalizować coś, co wykonuje swoje zadanie w ułamku sekundy? Co do punktu 2, czy kompilator nie jest na tyle bystry, żeby policzyć wartość funkcji dla stałej tylko raz? Ten algorytm pomimo beznadziejnej implementacji (mam gdzieś napisane to samo w asmie, wbrew pozorom nie jest dużo szybsze) i tak jest dużo lepszy niż sprawdzanie dla każdej liczby z zakresu 1-1000000 czy jest pierwsza.

arigo · Post autor: **arigo** » 17 gru 2005, o 13:34

taka wrodzona mania optymalizacji

ad pkt 2 to przy sicie to moze i nie ma az takiego znaczenia, po prostu ja nie lubie wdawac sie w zakladanie ze kompilator to zoptymalizuje

ale jak kolega max poprawi pkt 1 i 3 to na szybko bedzie mial w miare wydajny programik

pozdrawiam

(c)RaSz · Post autor: **(c)RaSz** » 20 gru 2005, o 04:34

Podstawową rzeczą w tym zagadnieniu jest to, czy szukamy liczb niewielkich, kilku~, kilkunastocyfrowych, czy też takich, co mają cyfr kilkadziesiąt tysięcy. A może setki milionów cyfr? Bowiem w każdym z tych przypadków – postępowanie będzie inne. Podobnie też – metody przybliżone. Bez określenia zakresu - każdy algorytm będzie kiepski
Metod optymalizacji jest dość sporo, przy czym niektóre – wzajemnie się gryzą, że się tak wyrażę. Jednak parę zaleceń natury ogólnej – można by tu wspomnieć, zanim jeszcze koledzy widescreen, oraz max zadeklarują, jakie zakresy liczbowe są im potrzebne...
Pomijanie liczb, które pierwszymi być nie mogą, żadną miarą... Otóż powyżej liczby 3, wszystkie liczby pierwsze występują tylko i wyłącznie w dwóch ciągach, wyrażających się równaniem: \(\displaystyle{ p_x = 6 n +/- 1}\) – więc tylko \(\displaystyle{ 1/3}\)-cia liczb jest w ogóle warta sprawdzania...
Oszczędzanie pamięci: niezłą sztuczką, którą stosujemy, przechodząc do liczb naprawdę dużych, jest ich zapamiętywanie w zadeklarowanej tablicy, jako pojedynczych bitów (sic !.) Przy czym liczby pierwsze pozostają zapalone (bit=1), zaś znajdowane liczby złożone gasimy (bit=0). Albo odwrotnie, wszak to tylko kwestia umowy, no i wygody.
W przypadku E-sita ważne jest zagnieżdżenie (kolejność wykonywania) pętli iteracyjnych. Czasem lepiej jest dać jako zewnętrzną pętlę podnoszącą liczbę badaną, zaś wewnątrz niej przebiegać przez już znalezione, mniejsze liczby pierwsze, zaś czasem – wygodniej jest zrobić na odwrót, co pozwala wyeliminować mnożenie, a posługiwać się wyłącznie dodawaniem, które idzie deczko szybciej...

Zaś co do testów, badających czy liczba jest pierwsza: w przypadku, gdy chodzi o naprawdę duże liczby, to oczywiście nie bada się ich podzielności przez wszystkie, które by mogły wchodzić w grę, bo zajęło by to całe lata. Stosuje się skrócone testy na „pierwszość”. Szukaj być ich kilka...

Możesz się też posłużyć moim rzeszotem.

arigo · Post autor: **arigo** » 20 gru 2005, o 15:00

(c)RaSz pisze:Stosuje się skrócone testy na „pierwszość”.

afaik takie testy daja pewnosc ze liczba jest pierwsza rzedu 99,9999999999% a to jest zadna pewnosc i liczba nie moze zostac uznana za pierwsza jesli nie sprawdzisz jej "klasycznie" tzn sitem lub sposobem opisywanym wczensiej przeze mnie

juzef · Post autor: **juzef** » 20 gru 2005, o 17:24

arigo pisze:liczba nie moze zostac uznana za pierwsza jesli nie sprawdzisz jej "klasycznie" tzn sitem lub sposobem opisywanym wczensiej przeze mnie

Na szczęście może. Istnieją agorytmy dające pewność czy liczba jest pierwsza czy złożona działające znacznie szybciej. można znaleźć program, który dość sprawnie potrafi sprawdzić pierwszość liczby.

arigo · Post autor: **arigo** » 20 gru 2005, o 20:17

juzef pisze:Na szczęście może. Istnieją agorytmy dające pewność czy liczba jest pierwsza czy złożona działające znacznie szybciej.

mhm

nie znalem ich - dlatego napisalem afaik

neworder · Post autor: **neworder** » 20 gru 2005, o 23:26

Notabene, dla potrzeb kryptograficznych etc. wystarczają algorytmy probabilistyczne z ryzykiem błędu rzędu miliardowych części procenta.

(c)RaSz · Post autor: **(c)RaSz** » 22 gru 2005, o 06:04

Jak pisze na swojej pełne testowanie liczby raptem ~120-cyfrowej, wg sposobu proponowanego przez Arigo mogłoby szybkiemu komputerowi zająć ca 930697189301371180949082 razy dłużej, niż obecnie szacowany czas istnienia... Wszechświata - Zaś w kryptologii stosuje się liczby jeszcze większe... Dlatego rzadko kto ma ochotę upierać się przy metodach w pełni deterministycznych... Nawet takich sprytnych, jak APR Najczęściej stosuje się probabilistyczny test Rabina-Millera.

Na zbliżony temat skrobnąłem też słówko w poście pomysł... pilnie poszukiwany pomysł, więc nie będę tu powtarzał, zajrzyj tam.

Dave · Post autor: **Dave** » 25 gru 2005, o 21:33

A czy ktos wspominal juz o algorytmie shora? Bardzo ciekawy i w miare prosty algorytm sprawdzajacy pierwszosc liczby, ktory prawdopodobnie znajdzie zastosowanie w komputerach kwantowych, choc przy ich mocy obliczeniowej moze sie to okazac zbedne

[ Dodano: Czw Gru 29, 2005 11:26 am ]
Sprostowanie: nie dotyczytalem topicu, oczyiwscie algorytm shora to algorytm rozkladu liczby na czynniki pierwsze, sorry