Mam jedno małe pytanko, nie chcę specjalnie zakładać nowego tematu. Czy istnieje algorytm generujący nieskończony ciąg liczb pierwszych?
To pytanie z egzaminu z logiki algorytmicznej.
Popatrzmy na pewien algorytm, który produkuje liczby pierwsze:
Weźmy dowolną liczbę i zacznijmy ją dzielić przez liczby, które są od niej mniejsze, jest ich pewnie skończenie wiele. Jeżeli wszystkie takie liczby podzielą z resztą, oznacza to, że jest ona liczbą pierwszą.
Ten algorytm jest dosyć dobry, ale przy bardzo dużych liczbach, łatwo o pomyłkę.
Innym algorytmem, polegającym na rozkładaniu liczby na liczby pierwsze jest faktoryzacja.
Przykład faktoryzacji:
15=3*5 100=5*5*2*2
Jeśli liczbę można przedstawić w taki właśnie sposób to nie jest ona liczbą pierwszą, ale ten sposób jest sposobem jeszcze bardziej nieefektywnym niż wcześniejszy.
Aby znaleźć wszystkie liczby pierwsze, które nie są większe od z góry zadanej liczby n, można się posłużyć następującym sposobem, zwanym "sitem Eratostenesa". Należy wypisać w porządku wszystkie liczby naturalne od 2 do n. Pierwsza z tych liczb jest liczbą pierwszą. Zostawiamy ją i następnie wykreślamy wszystkie liczby, które dzielą się przez dwa, a ponieważ się dzielą przez dwa to nie są pierwsze. W praktyce oznacza to, że wykreślamy wszystkie parzyste liczby. Jeśli to już zrobimy, pierwszą liczbą po 2 jest 3. Jest ona liczbą pierwszą. Zostawiamy ją i następnie wykreślamy wszystkie liczbą, które dzielą się przez 3. Po tej operacji, kolejną liczbą, która nie została wykreślona jest 5. Jest ona liczbą pierwszą, więc ją zostawiamy i wykreślamy z pozostałych wszystkie te, które dzielą się przez 5. Jeśli będziemy kontynuować to wykreślanie w ten sposób otrzymamy wszystkie liczby pierwsze mniejsze od liczby n.
Niestety i ta metoda nie jest najlepsza. Przy bardzo dużych liczbach, obliczenia trwają zbyt długo, aby stosować go na dłuższą metę.
Najlepszym sposobem znajdowania liczb pierwszych jest posługiwanie się komputerem Cray z serii T90, wyposażonym w algorytm Lucasa-Lehmera. Sławni matematycy: David Slowinski - Paul Gage posiadają patent na posługiwanie się nim. Slowinski jest uważany za "łowcę" największych liczb pierwszych.
_______________________________
I will never be afraid again
I will keep on fighting 'till the end
I can walk on water, I can fly
I will keep on fighting till I die...
Poszperalem na necie i nie wiem
Ale tak na logike, skoro wciaz poznajemy nowe liczby pierwsze i wiemy ze na pewno wszystkich nigdy nie poznamy bo jest ich nieskonczonosc to chyba taki algorytm jest nie do ogarniecia(a na pewno nie w praktyce ze wzgledu na ograniczona moc obliczeniowa komputerow) ale w teorii wszystko jest mozliwe wiec niech sie wypowiedza lepiej teoretycy
_______________________________
I will never be afraid again
I will keep on fighting 'till the end
I can walk on water, I can fly
I will keep on fighting till I die...
faramka, gdyby cos takiego istnialo i bylo szybkie to szyfrowanie RSA nie mialoby sensu
ja nie slyszalem o czyms takim i na 99,99999% jestem pewny, ze czegos takiego nie ma (jedyna mozliwosc: najbardziej zaawansowane bazy wojskowe, ale to i tak mysle Science-Fiction )
Zmieniony przez - Kuba_SnK w dniu 2010-02-23 18:22:38
_______________________________
mafia inso-fizyków%-)
No właśnie, wydaje się, że nie ma takiej pieprzonej możliwości, ale zagwozdka jest.
Dokładna treść zadania: Czy i dlaczego
a) istnieje
b) jest znany
c) został zrealizowany komputerowo
d) został wykonany bez komputera
algorytm generujący nieskończony ciąg liczb pierwszych?
Znaczy: każdy podpunkt trzeba uzasadnić.
Dzięki, chłopaki, za szybką reakcję.
Zmieniony przez - faramka w dniu 2010-02-23 18:23:51
_______________________________
[www.bike.sandomierz.org]
chyba, ze chodzi Ci o jakie naiwne testy typu ... znamy liczby pierwsze:
2,3,5,7 i chcemy liczyc dalej
sprawdzamy 8 ... dzieli sie przez 2 ... nie jest pierwsza...
sprawdzamy 9 ... nie dzieli sie przez 2... dzieli sie przez 3 ... nie jest pierwszza
sprawdzamy 10 ... dzieli sie przez 2 -> nie jest
sprawdzamy 11 ... nie dzieli sie przez 2... nie dzieli sie przez 3 ... nie dzieli sie przez 5 ... nie dzieli sie przez 7 ... jest pierwsza
itd (chyba wystarczy sprawdzac do liczb pierwszych <= sqrt(liczba) )
bo jesli to nazwiemy algorytmem generujacym nieskonczony ciag liczb pierwszych (defacto mozna nim dostac kazda liczbe pierwsza ... tylko ze takie 10^100 to "troche" beda trwaly ... edyna nadzieja to kompy kwantowe)
Zmieniony przez - Kuba_SnK w dniu 2010-02-23 18:26:28
_______________________________
mafia inso-fizyków%-)
i powiem Ci szczerze, ze zaznaczylbym raczej w tym wypadku wszystkie, ze:
istnieje
jest znany
zostal zrealizowany komputerowo
zostal wykonany bez komputera (na kartce tez mozemy sprawdzac )) )
ale pytanie jest mocno glupie, albo ja sie za bardzo zastanawiam nad tym co sie kryje pod "algorytm generujacy nieskonczony ciag liczb pierwszych"
_______________________________
mafia inso-fizyków%-)
Sama nie wiem, o co chodziło. Podejrzewam, że najważniejsze w zadaniu było uzasadnienie ( nie, bo... albo tak, bo... ).
Mhm, mogłam napisać nie wiem, czy istnieje, bo nie jest mi znany Ewentualnie wprowadzić człenia w zakłopotanie i odpowiedzieć istnieje (sama napisałam), ale nie jest znany, bo ukrywam go przed światem .
Zmieniony przez - faramka w dniu 2010-02-23 18:33:00
_______________________________
[www.bike.sandomierz.org]
istnieje - tym algorytmem, który podalem mozemy dostac kazda liczbe pierwsza (w teorii .. bo w praktyce doszedlem do 2^32 i plik mi 2Gb zajmowal + chwile trwalo ... a co dopiero 2^64 ) ... a to do nieskonczonosci daleko, ale ... mozna )
jest znany - wlasnie go pokazalem
zostal zrealizowany komputerowo - moge Ci wkleic kod
zostal wykonany bez komputera - ktos na 100% na kartce troche liczb policzyl
tak bym uzasadnial
Zmieniony przez - Kuba_SnK w dniu 2010-02-23 18:35:37
_______________________________
mafia inso-fizyków%-)
