Megállapítani egy számról, hogy prím-e?

A 2-3000 számjegyű számok osztása nem olyan vészes. A probléma az, hogy nagyon sok ilyen szám van.

A prímteszteket arra használják, hogy ezt a hatalmas mennyiséget leszűkítsék, és utána "hagyományos" módszerrel esnek neki a megmaradt számoknak.

Kedves _Jessy_ !

Ahogy zsomkovacs írta, 0-nál nagyobb a valószínűsége (még ha nagyon kicsi is), annak hogy egy jó hardver úgymond "téved", ehhez még képest is elhanyagolható annak az esélye, hogy a Miller Rabin teszt hibás eredményt ad.

Szeretjük a determinisztikus matematikailag helyes algoritmusokat, de a számítógép hardver-e nem a matematika szellemi világában létezik, hanem a fizikai valóságba, ahol figyelembe kell venni az elektorfizika, az elektrokémia-i stb hatásokat is.

Igaz hogy matematikailag kifogásolható a Miller Rabin teszt, matematikailag azt mondom osztogasd végig a szám négyzetgyökéig vagy akár a szám mínusz 1-ig, kit érdekel, a turing gép véges lépésszám alatt lefuttatja, helyes. A az Miller R teszt meg mint érdekesség van, de nem tökéletes.

CSAKHOGY nincs tökéletesen biztosan hibátlanul számoló számítógép, nincs turing gép a valóságba, és nem mindegy hogy fél másodperc alatt fut le a program vagy a naprendszer élettartama nem lenne elég rá, kitörölhetem a s...em hogy véges idő alatt lefut csak épp 100 trillió év lenne. Ennyi erővel ne számoljunk semmit számítógéppel mert meg van annak a valószínűsége hogy (elektorfizikai okok miatt) invertálódik egy bit, matematikai értelemben nincs helyes számítógép, csak mérnöki pontossággal. Várhatóan az életbe nemigen fogok tapasztalni ilyen fajta hibát mert olyan ritka, de ez nem számít mert megrögzött matematikus vagyok.

Szerintem indítasz egy ciklust

úgy hogy

i:2 től j-1ig

ha nem j=j/2 or j=j/3 or j=j/5 akkor a[m]:=j

valami ilyesminek kellene lennie azt hiszem