streamalism.org

1. Áttekintés

Két egész számot adunk meg, a és b, azt mondjuk, hogy azok viszonylag prím, ha az egyetlen tényező, amely mindkettőt megosztja, 1. A kölcsönösen a prím vagy a coprime a viszonylag prímszámok szinonimája.

Ebben a gyors bemutatóban áttekintjük a probléma megoldását a Java segítségével.

2. Legnagyobb közös tényező algoritmus

Mint kiderült, ha a legnagyobb közös osztó (gcd) 2 számból áll a és b értéke 1 (azaz gcd (a, b) = 1) azután a és b viszonylag elsődlegesek. Ennek eredményeként annak megállapítása, hogy két szám viszonylag prím, egyszerűen abból áll, hogy megállapítjuk, hogy a gcd az 1.

3. Euklideszi algoritmus megvalósítása

Ebben a szakaszban az euklideszi algoritmust fogjuk használni az gcd 2 számból.

Mielőtt bemutatnánk megvalósításunkat, foglaljuk össze az algoritmust, és nézzünk meg egy gyors példát arra, hogyan alkalmazzuk az érthetőség kedvéért.

Képzeljük el, hogy két egész számunk van, a és b. Az iteratív megközelítésben először megosztunk a által b és megkapja a maradékot. Ezután hozzárendeljük a az értéke b, és hozzárendeljük b a fennmaradó érték. Ezt a folyamatot addig ismételjük, amíg b = 0. Végül, amikor elérjük ezt a pontot, visszaadjuk a a mint a gcd eredmény, és ha a = 1, azt mondhatjuk a és b viszonylag elsődlegesek.

Próbáljuk ki két egész számmal, a = 81 és b = 35.

Ebben az esetben a fennmaradó 81 és 35 (81 % 35) van 11. Tehát az első iterációs lépésben ezzel fejezzük be a = 35 és b = 11. Következésképpen egy újabb iterációt hajtunk végre.

A fennmaradó rész 35 osztva 11 van 2. Ennek eredményeként most van a = 11 (értékeket cseréltünk) és b = 2. Folytassuk.

Még egy lépés eredményez a = 2 és b = 1. Most a végéhez közeledünk.

Végül még egy ismétlés után elérjük a = 1 és b = 0. Az algoritmus visszatér 1 és arra következtethetünk 81 és 35 valóban viszonylag elsődlegesek.

3.1. Kötelező megvalósítás

Először valósítsuk meg az euklideszi algoritmus kötelező Java verzióját a fent leírtak szerint:

int iteratívGCD (int a, int b) {int tmp; míg (b! = 0) {if (a <b) {tmp = a; a = b; b = tmp; } tmp = b; b = a% b; a = tmp; } return a; } 

Mint észrevehetjük, abban az esetben, ha a kevesebb mint b, a folytatás előtt felcseréljük az értékeket. Az algoritmus leáll, amikor b értéke 0.

3.2. Rekurzív megvalósítás

Ezután nézzünk meg egy rekurzív megvalósítást. Ez valószínűleg tisztább, mivel elkerüli az explicit változóérték-csereügyleteket:

int rekurzívGCD (int a, int b) {if (b == 0) {return a; } if (a <b) {visszatér rekurzívGCD (b, a); } return recursiveGCD (b, a% b); } 

4. Használata BigIntegerVégrehajtása

De várj - nem az gcd algoritmus már megvalósult a Java-ban? Igen, ez az! A BigInteger osztály biztosítja a gcd módszer, amely az euklideszi algoritmust valósítja meg a legnagyobb közös osztó megtalálásához.

Ezzel a módszerrel könnyebben elkészíthetjük a viszonylag elsődleges algoritmust:

logikai nagyIntegerRelativePrime (int a, int b) {return BigInteger.valueOf (a) .gcd (BigInteger.valueOf (b)). egyenlő (BigInteger.ONE); } 

5. Következtetés

Ebben a gyors bemutatóban bemutattuk a megoldást arra a problémára, hogy a két megvalósítás segítségével megállapítsuk, hogy két szám viszonylag prím-e gcd algoritmus.

És mint mindig, a mintakód elérhető a GitHubon.