streamalism.org

1. Oversikt

Gitt to heltall, en og b, vi sier at de er det relativt prime hvis den eneste faktoren som deler begge er 1. Gjensidig prime eller coprime er synonymer for relativt primtall.

I denne raske opplæringen går vi gjennom en løsning på dette problemet ved hjelp av Java.

2. Største algoritme for vanlig faktor

Som det viser seg, hvis den største felles divisoren (gcd) av 2 tall en og b er 1 (dvs. gcd (a, b) = 1) deretter en og b er relativt førsteklasses. Som et resultat, bestemmer om to tall er relativt primære, bare å finne ut om gcd er 1.

3. Implementering av euklidisk algoritme

I denne delen bruker vi den euklidiske algoritmen til å beregne gcd på 2 tall.

Før vi viser implementeringen vår, la oss oppsummere algoritmen og se på et raskt eksempel på hvordan du bruker den for forståelsens skyld.

Tenk deg at vi har to heltall, en og b. I den iterative tilnærmingen deler vi oss først en av b og få resten. Deretter tildeler vi en verdien av b, og vi tildeler b restverdien. Vi gjentar denne prosessen til b = 0. Til slutt, når vi når dette punktet, returnerer vi verdien av en som gcd resultat, og hvis en = 1, vi kan si det en og b er relativt førsteklasses.

La oss prøve det på to heltall, a = 81 og b = 35.

I dette tilfellet er resten av 81 og 35 (81 % 35) er 11. Så i det første iterasjonstrinnet slutter vi med a = 35 og b = 11. Derfor vil vi gjøre en ny iterasjon.

Resten av 35 delt på 11 er 2. Som et resultat har vi nå a = 11 (vi byttet verdier) og b = 2. La oss fortsette.

Ett trinn til vil resultere i a = 2 og b = 1. Nå nærmer vi oss slutten.

Til slutt, etter en gjentakelse til, når vi a = 1 og b = 0. Algoritmen kommer tilbake 1 og det kan vi konkludere med 81 og 35 er faktisk relativt førsteklasses.

3.1. Imperativ implementering

La oss først implementere den tvingende Java-versjonen av den euklidiske algoritmen som beskrevet ovenfor:

int iterativGCD (int a, int b) {int tmp; mens (b! = 0) {if (a <b) {tmp = a; a = b; b = tmp; } tmp = b; b = a% b; a = tmp; } returner a; } 

Som vi kan merke, i tilfelle der en er mindre enn b, bytter vi verdiene før vi fortsetter. Algoritmen stopper når b er 0.

3.2. Rekursiv implementering

La oss deretter se på en rekursiv implementering. Dette er sannsynligvis renere siden det unngår eksplisitte bytter med variabel verdi:

int rekursivGCD (int a, int b) {if (b == 0) {return a; } hvis (a <b) {return rekursivGCD (b, a); } returner rekursivGCD (b, a% b); } 

4. Bruke BigInteger‘S Implementering

Men vent - er ikke det gcd algoritme allerede implementert i Java? Ja, det er det! De BigInteger klasse gir en gcd metode som implementerer den euklidiske algoritmen for å finne den største felles divisoren.

Ved hjelp av denne metoden kan vi lettere utarbeide den relativt viktigste algoritmen som:

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

5. Konklusjon

I denne raske opplæringen har vi presentert en løsning på problemet med å finne ut om to tall er relativt primære ved hjelp av tre implementeringer av gcd algoritme.

Og som alltid er eksempelkoden tilgjengelig på GitHub.