Megnézed, hogy osztható-e 2-vel. Aztán 3-tól kettesével lépkedve egy ciklusban elmész a szám négyzetgyökéig, és minden egyes számmal megnézed, hogy osztható-e vele. Ha bármelyikkel is osztható (akár a 2-vel, akár a páratlan számok valamelyikével), akkor nem prímszám. Ezt legegyszerűbben úgy tudod számon tartani, hogy a 2-vel való osztás előtt egy logikai változónak true értéket adsz, ha valamivel oszthatónak találod, akkor meg ennek false értéket adsz. A végén meg ha true maradt, akkor prím, ha false, akkor nem prím. Gyorsíthatod a tesztet, ha a ciklusból azonnal kilépsz, amint oszthatóságot találsz.
2012. jan. 14. 10:13
Hasznos számodra ez a válasz?
2/19 anonim válasza:
Végigmész a számnál kisebb számokon, és mindíg ellenőrződ, hogy ha az adott számmal elosztod ( az eredetit ) 0-át kapsz-e.
2012. jan. 14. 10:13
Hasznos számodra ez a válasz?
3/19 A kérdező kommentje:
Köszi szépen, remélem siker.
2012. jan. 14. 10:26
4/19 anonim válasza:
A fentiek is eredményhez vezetnek, de egy pl 100 számjegyű számnál már valszeg nem elég hatékonyak.
Ezek alapján már el tudsz indulni. Én a Miller Rabin tesztet használnám!
2012. jan. 14. 10:28
Hasznos számodra ez a válasz?
5/19 _Jessy_ válasza:
"...választásra igaz a fenti állítás, akkor n nagy valószínűséggel prím." Ezért nem választanám a Miller-Rabin-t :) Lehet, hogy statisztika tantárgy esetén elfogadható, de matematikailag nem nagyon :D
2012. jan. 14. 10:36
Hasznos számodra ez a válasz?
6/19 _Jessy_ válasza:
Egyébként a feladat lényege sztem nem a programozás, hanem hogy megtaláld a megfelelő algoritmust, ezt kellett volna egyedül csinálnod. Leprogramozni egy kész algoritmust nem egy nagy dolog.
2012. jan. 14. 10:39
Hasznos számodra ez a válasz?
7/19 zsomkovacs válasza:
#5: ha mondjuk 200 különböző alappal megcsinálod a Miller-Rabint, és mindig azt adja ki, hogy prím, akkor már jelentősen nagyobb az esélye annak, hogy a számítógép hardver szinten elront valamit, mint hogy a szám mégsem prím.
Ez a prímtesztek nagy részére nem igaz (pl. kis-Fermat esetén a Carmichael-számok), de a Miller-Rabin éppen ilyen, ezért is használják igen elterjedten.
Más kérdés, hogy valószínűleg a kérdezőnek nem pont erre van szüksége.
2012. jan. 14. 10:46
Hasznos számodra ez a válasz?
8/19 anonim válasza:
Igen, a prímtesztek csak nagy valószínűséggel mondják meg a számról, hogy prím-e, de az a helyzet, hogy tetszőlegesen nagy számokra a számokkal való osztás nem hatékony. Próbáld ki 2-300 esetleg 2-3000 számjegű számra. Biztos vagyok benne, hogy a program futási ideje, memória használata jelentősen több lesz, mint bármelyik prímteszté
2012. jan. 14. 10:49
Hasznos számodra ez a válasz?
9/19 _Jessy_ válasza:
"...nagyobb az esélye annak, hogy a számítógép hardver szinten elront valamit..." Ne haragudj, de ez mit is jelent pontosan? Ha elrontja, hibás a hardver :) Esetleg lebegőpontosnál elronthatja, de általában prímtesztet egészre végzik. Másfelől pedig nálam a valószínűleg igen nem igent jelent :) Én már csak ilyen földhözragadt vagyok :)
2012. jan. 14. 10:55
Hasznos számodra ez a válasz?
10/19 _Jessy_ válasza:
#8
A szimpla osztásos módszernél 2-3 ezer jegy esetén a proram futási ideje tényleg nagyon nagy lesz, de a memóriahasználat nem annyira. De mindegy, gondolom itt azért nem az a lényeg, hogy ilyen nagy számokra csináljunk prímtesztet.
A weboldalon megjelenő anyagok nem minősülnek szerkesztői tartalomnak, előzetes ellenőrzésen nem esnek át, az üzemeltető véleményét nem tükrözik. Ha kifogással szeretne élni valamely tartalommal kapcsolatban, kérjük jelezze e-mailes elérhetőségünkön!
válasza: