Hogyan lehet megmondani, csak Windows-számológép segítségével, hogy az alábbi 4 szám közül melyik 2 prím?
27 000 001, 30 000 001, 33 000 001, 36 000 001
Tudjuk, hogy PONTOSAN 2 db prím van közöttük.
válasza:Egyszerűbbet nem tudok:
Az adott számot a gyökéig oszd el pozitív egész számokkal.
Ha gyökökkel osztasz csak, akkor gyorsabb, és ugyanúgy jó.
Osztás helyett használhatod a Tudományos nézetben lévő modulo műveletet (Mod), de igazából nem gyorsít szerintem.
válasza:De csalok, hogy legyen megoldásod az ellenőrzéshez:
27 000 001 = 7*43*271*331
30 000 001 prím
33 000 001 prím
36 000 001 = 37*269*3617
válasza:"Egyszerűbbet nem tudok:
Az adott számot a gyökéig oszd el pozitív egész számokkal."
:D
Más megoldásnak is kell lenni, mint 5-6000-ig osztogatni.
válasza:Az a^p -t hogy számolod ki a Windows-számológépével?
Ezekre felesleges megnézni: a = -1, a = 0, a = 1
a = 2 -re meg már túl nagy szám lenne nálam legalábbis.
Érdekelne, hogyan sikerült használnod.
p csak akkor LEHET prím, ha 2^(p-1) mod p = 1
(Ha nem 1, akkor biztosan nem prím.)
A Windows-számológép az egészekkel teljes hosszúságban/pontossággal számol.
A moduláris hatványozás több részletben is elvégezhető, - kitevő szorzatra bontás, - így pl. p=30 000 001 esetén:
2^30 000 000 mod p =
(2^30000 mod p)^1000 mod p = 13607516^1000 mod p = 1
vagy akár
(((2^100 mod p)^100 mod p)^100 mod p)^30 mod p = 1
A 2. és 3. számnál ez a maradék 1, az 1. és 4.-nél nem 1, így csak a 2.-3. lehetnek prímek.
És "Tudjuk, hogy PONTOSAN 2 db prím van közöttük."
Remélem érthetően írtam.
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!