(Fontos! ) Hogy lehet megállapítani egy (nagy) számról, hogy prím-e, és ha nem prím, akkor mi a legnagyobb és legkisebb osztója?
válasza:Ez neked mióta nagy szám?…
Amúgy 35 728 783 116 357 = 3 * 1 245 863 * 9 559 313.
Másrészt, hogy prímek-e, azt tényleg nagy számokról különféle prímtesztekkel szokták. Itt olvashatsz róluk részletesen: [link]
A legnagyobb osztójuk: az egyszerű, önmaguk.
A legkisebb osztójuk: ez se bonyolult, ha negatív osztókat is megengedünk, akkor a –1-szeresük, különben meg az 1.
A legkisebb/legnagyobb VALÓDI osztójuk: no ez az, ami tud szívás lenni, és nem ismert rá általában gyors módszer. (Amúgy azért vettem őket egy kalap alá, mert ha az egyikkel elosztod a számot, akkor a másikat kapod.)
válasza: válasza:Oszthatósági szabályokkal.
Ha 5-re vagy 0-ra végződik, akkor ugye osztható 5-tel.
Ha párosra, akkor 2-vel.
Ha a számjegyek összege osztható 3-mal, akkor a szám is.
Ebből meg már kijön minden. :)
válasza: válasza: válasza:Randomizált prímtesztekkel, mint amilyen a Miller-Rabin prímteszt, egész nagy (több száz jegyű) számokról is elég nagy valószínűséggel meg lehet állapítani, hogy prímszámok-e.
A példádban szereplő szám ezekhez képest nagyon kicsi.
Az osztóiról csak akkor lehet mondani valamit, ha sikerül prímtényezők szorzatára bontani.
A legnaivabb módszer egy X szám felbontására, hgy gyök X-ig bezárólag egyesével végigosztjuk, és ha maradék nélkül sikerül ezt megtenni, akkor az eredménnyel kezdjük a folyamatot elölről.
Az általad megadott szám 14 jegyű, a gyöke kb. 7 jegyű, ezt még simán meg lehet csinálni egy számítógéppel.
Több száz jegyű számok esetén már nem, mert egyszerűen nagyon sokáig tartana.
Nagyobb számokkal a kvadratikus szita, és a számtest szita esetleg meg tud bírkózni, de ezeknek a futási ideje sem arányos a számjegyek számával, lesz egy határ, ahol a futási idő csúnyán "elszáll".
Ezt a tényt használja a ki az RSA nevű titkosítási módszer.
Számomra az 1 millió is nagynak számít már :), a kérdésemben pedig a valódi osztókra gondolok. Tehát hogy egy nagyon nagy szám legkisebb és legnagyobb valódi osztóját hogy lehet legkönnyebben, számítógép használata nélkül megtudni, illetve az adott számról számítógép használata nélkül hogy lehet megállapítani, hogy prím.
És mindenkinek köszönöm a válaszokat! Az első válaszolótól meg szeretném még kérdezni, hogy nem tudsz belinkelni olyat, ahol magyarul is leírják? Előre is köszönöm.
válasza:1. megtanulod a prímszámokat. Ha csak 1.000.000-ig akarsz minden számot felbontani fejben, vagy papíron, akkor elég csak 1000-ig megjegyezni őket.
2. megpróbálod a számot elosztani velük.
A jó hír az, hogy ha a szám véletlenszerűen lett kiválasztva, akkor az esetek felében rögtön osztható lesz kettővel :) (A páratlan számok közül sok osztható 3-mal, 5-tel, vagy 7-tel.)
Az egész számok felbontása sajnos ténylegnehéz feladat.
Kapcsolódó kérdések:
Minden jog fenntartva © 2024, www.gyakorikerdesek.hu
GYIK | Szabályzat | Jogi nyilatkozat | Adatvédelem | Cookie beállítások | WebMinute Kft. | Facebook | Kapcsolat: info(kukac)gyakorikerdesek.hu
Ha kifogással szeretne élni valamely tartalommal kapcsolatban, kérjük jelezze e-mailes elérhetőségünkön!