streamalism.org

1. Prehľad

Vzhľadom na dve celé čísla, a a b, hovoríme, že sú relatívne prvočíslo, ak jediný faktor, ktorý obidve rozdeľuje, je 1. Vzájomne prime alebo coprime sú synonymá pre relatívne prvočísla.

V tomto rýchlom návode si ukážeme riešenie tohto problému pomocou jazyka Java.

2. Najväčší algoritmus spoločného faktora

Ako sa ukazuje, ak je najväčší spoločný deliteľ (gcd) z 2 čísel a a b je 1 (t.j. gcd (a, b) = 1) potom a a b sú relatívne prime. Výsledkom je, že určenie, či sú dve čísla relatívne prvočíselné, spočíva jednoducho v zistení, či gcd je 1.

3. Implementácia euklidovského algoritmu

V tejto časti použijeme na výpočet Euklidovský algoritmus gcd z 2 čísel.

Predtým, ako ukážeme našu implementáciu, zhrňme si algoritmus a pozrime sa na rýchly príklad, ako ho v záujme pochopenia použiť.

Predstavte si teda, že máme dve celé čísla, a a b. Pri iteračnom prístupe najskôr rozdelíme a od b a získajte zvyšok. Ďalej priradíme a hodnota b, a my priradíme b zvyšná hodnota. Tento postup opakujeme až do b = 0. Nakoniec, keď dosiahneme tento bod, vrátime hodnotu a ako gcd výsledok, a ak a = 1, to môžeme povedať a a b sú relatívne prime.

Vyskúšajme to na dvoch celých číslach, a = 81 a b = 35.

V takom prípade zostáva zvyšok 81 a 35 (81 % 35) je 11. Takže v prvom iteračnom kroku končíme a = 35 a b = 11. Následne urobíme ďalšiu iteráciu.

Zvyšok 35 deleno 11 je 2. Výsledkom je, že teraz máme a = 11 (zamenili sme hodnoty) a b = 2. Pokračujme.

Výsledkom bude ešte jeden krok a = 2 a b = 1. Teraz sa blížime ku koncu.

Nakoniec sa dočkáme ešte jednej iterácie a = 1 a b = 0. Algoritmus sa vráti 1 a môžeme z toho vyvodiť záver 81 a 35 sú skutočne relatívne najlepšie.

3.1. Záväzná implementácia

Najskôr implementujme imperatívnu verziu Euklidovského algoritmu Java, ako je popísané vyššie:

int iterativeGCD (int a, int b) {int tmp; while (b! = 0) {if (a <b) {tmp = a; a = b; b = tmp; } tmp = b; b = a% b; a = tmp; } vrátiť a; } 

Ako si môžeme všimnúť, v prípade, že a je menej než b, pred pokračovaním zameníme hodnoty. Algoritmus sa zastaví, keď b je 0.

3.2. Rekurzívna implementácia

Ďalej sa pozrime na rekurzívnu implementáciu. Toto je pravdepodobne čistejšie, pretože sa vyhýba explicitným výmenám variabilných hodnôt:

int recursiveGCD (int a, int b) {if (b == 0) {return a; } if (a <b) {return recursiveGCD (b, a); } návratová rekurzívnaGCD (b, a% b); } 

4. Používanie BigIntegerImplementácia

Ale počkajte - nie je gcd algoritmus už implementovaný v Jave? Áno, je! The BigInteger trieda poskytuje a gcd metóda, ktorá implementuje euklidovský algoritmus na nájdenie najväčšieho spoločného deliteľa.

Pomocou tejto metódy môžeme ľahšie navrhnúť relatívne prime algoritmus ako:

boolean bigIntegerRelativelyPrime (int a, int b) {return BigInteger.valueOf (a) .gcd (BigInteger.valueOf (b)). equals (BigInteger.ONE); } 

5. Záver

V tomto rýchlom návode sme predstavili riešenie problému zistenia, či sú dve čísla relatívne prvočíselné, pomocou troch implementácií gcd algoritmus.

A ako vždy je vzorový kód k dispozícii na GitHub.