Algorytm wyszukiwania liczb pierwszych

arigo · Post autor: **arigo** » 4 lis 2004, o 19:02

bo nie doszedles do pewnej wartosci granicznej

btw liczb pierwszych wezcie sobie ustawcie wyswietlanie liczb zamiast dziesietnie to binarnie 8 najmniej znaczacych bitow a potem tesame 8 bitow tylko odwrocne tak zeby os symetrii utworzyc

fajne efkety wizualne jak sie takie cos pusci na konsole tylko ze sleep(10) na kazda liczbe kosmici domki smoki etc

Hetacz · Post autor: **Hetacz** » 4 lis 2004, o 19:04

Nie pomyślałem o tym, choć jak narazie program sprawuje się dobrze.

MatS · Post autor: **MatS** » 4 lis 2004, o 21:29

hej swego czasu napisalem program we free pascalu ktory sprawdzal czy liczby postaci m=3^n+2 sa pierwsze...i doszedlem do wyniku dla n=4346 zajelo to 4806,33 [s] wykorzystalem tu propabilistyczny test pierwszosci opisany bodajrze w II tomie Knutha...jesli chcialbys wiedziec wiecej daj cynka...postaram sie to jakos opisac...choc gdzies juz to opisywalem na tym forum...wiec mozesz tez gdzies poszperac...

arigo · Post autor: **arigo** » 4 lis 2004, o 21:31

tylko ze i tak takie liczby trzeba potem sprawdzic testem nieprobabilistycznym

gnicz · Post autor: **gnicz** » 4 lis 2004, o 21:32

Wtedy mozna stosowac wolniejsze metody (gdy test probabilistyczny da wynik pozytywny) np. oparte o krzywe eliptyczne.

Pozdrawiam, GNicz

MatS · Post autor: **MatS** » 4 lis 2004, o 21:35

ten test propabilistyczny okresla nam pierwszosc liczb z bardzo duzym prawdopodobienstwem

gnicz · Post autor: **gnicz** » 4 lis 2004, o 21:40

... ale mniejszym niz 1.

Pozdrawiam, GNicz

arigo · Post autor: **arigo** » 4 lis 2004, o 21:41

dokladnie
dopoki prawdopodienstwo nie bedzie wynosic 0,(9) to i tak i tak musisz przeprowadzic test nieprobabilistyczny

Hetacz · Post autor: **Hetacz** » 5 lis 2004, o 14:44

A czy istnieje jakaś łatwa do zaimplementowania metoda, która jest poprostu wydajniejsza od sita??

Zastosowanie metody nieprobablistycznej i probablistycznej naraz spowoduje spadadek wydajności programu

gnicz · Post autor: **gnicz** » 5 lis 2004, o 23:08

Mozesz analizowac liczby postaci 6k+1 i 6k-1 dla k "e" N. Zapamietujesz wszystkie znalezione liczby pierwsze w tablicy i dzielisz analizowana liczbe przez wszystkie zapamietane liczby pierwsze mniejsze lub rowne pierwiastkowi kwadratowemu sprawdzanej liczby. Sito ta najmniej wydajny algorytm.

Pozdrawiam, GNicz

Gregsky · Post autor: **Gregsky** » 6 lis 2004, o 11:01

ha! a ja policzyłem silnie ze 100 000.liczba ta ma około 475 000 cyfr.Jeśli mogę na takich dużych liczbach operować,to z pewnością liczbę pierwszą o podobnej ilosci cyfr też znajde.

Silnia ta liczyła się około 1,5 sekundy (Duron 1,7GHz) za pomocą pakietu Mathematica 4.

arigo · Post autor: **arigo** » 6 lis 2004, o 13:14

lol
to tez masz czym szpanowac
jakbys sam zakodowal program co taka silnie liczy w takim czasie to rozumiem ale chwalic sie odpaleniem czyjegos progsa to jest conajmniej dziwne

Dave · Post autor: **Dave** » 6 lis 2004, o 13:30

W sumie.... za to ja sie pochwale ze wczoraj zrobilem moj drugi progs! Przelicza stopy na metry, hehehhehe wiem ze to podstawowe cwiczenie w kazdej ksiazce znajdujace sie na trzeciej stronie ale i tak sie ciesze

Hetacz · Post autor: **Hetacz** » 6 lis 2004, o 13:56

Qrde normalnie ja niemogę jestem pod wrażeniem

Zawszę o tym marzyłem program co przelicza stopy na metry normalnie super.

Musisz być normalnie mózg informatyczno matematyczny, pewno wykłądasz na 5 uniwerkach i masz 10 honoris causów

Dave · Post autor: **Dave** » 6 lis 2004, o 14:08

Stary, przeciez jaja sobie robie