Find, hvis to numre er relativt primære i Java
1. Oversigt
Givet to heltal, -en og b, vi siger, at de er det relativt primær, hvis den eneste faktor, der deler begge dele, er 1. Gensidigt primær eller coprime er synonymer for relativt primtal.
I denne hurtige vejledning gennemgår vi en løsning på dette problem ved hjælp af Java.
2. Største fælles faktoralgoritme
Som det viser sig, hvis den største fælles skiller (gcd) af 2 tal -en og b er 1 (dvs. gcd (a, b) = 1) derefter -en og b er relativt førsteklasses. Som et resultat, at bestemme, om to tal er relativt primære, består simpelthen i at finde ud af om gcd er 1.
3. Implementering af euklidisk algoritme
I dette afsnit bruger vi den euklidiske algoritme til at beregne gcd på 2 tal.
Inden vi viser vores implementering, lad os sammenfatte algoritmen og se på et hurtigt eksempel på, hvordan vi anvender den af hensyn til forståelsen.
Så forestil dig, at vi har to heltal, -en og b. I den iterative tilgang deler vi først -en ved b og få resten. Derefter tildeler vi -en værdien af b, og vi tildeler b restværdien. Vi gentager denne proces indtil b = 0. Endelig når vi når dette punkt, returnerer vi værdien af -en som den gcd resultat, og hvis -en = 1, det kan vi godt sige -en og b er relativt førsteklasses.
Lad os prøve det på to heltal, a = 81 og b = 35.
I dette tilfælde er resten af 81 og 35 (81 % 35) er 11. Så i det første iterationstrin slutter vi med a = 35 og b = 11. Derfor foretager vi endnu en iteration.
Resten af 35 divideret med 11 er 2. Som et resultat har vi nu a = 11 (vi byttede værdier) og b = 2. Lad os fortsætte.
Et yderligere trin vil resultere i a = 2 og b = 1. Nu nærmer vi os slutningen.
Endelig når vi endnu en iteration, når vi a = 1 og b = 0. Algoritmen vender tilbage 1 og det kan vi konkludere 81 og 35 er faktisk relativt prime.
3.1. Imperativ implementering
Lad os først implementere den bydende Java-version af den euklidiske algoritme 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; } returnere a; } Som vi kan bemærke, i det tilfælde hvor -en er mindre end b, bytter vi værdierne, inden vi fortsætter. Algoritmen stopper når b er 0.
3.2. Rekursiv implementering
Lad os derefter se på en rekursiv implementering. Dette er sandsynligvis renere, da det undgår eksplicitte swaps med variabel værdi:
int rekursivGCD (int a, int b) {if (b == 0) {return a; } hvis (a <b) {return rekursivGCD (b, a); } returnere rekursivGCD (b, a% b); } 4. Brug BigInteger'S Implementering
Men vent - er det ikke gcd algoritme, der allerede er implementeret i Java? Ja det er! Det BigInteger klasse giver en gcd metode, der implementerer den euklidiske algoritme til at finde den største fælles skiller.
Ved hjælp af denne metode kan vi lettere udarbejde den relativt primære algoritme som:
boolsk bigIntegerRelativelyPrime (int a, int b) {return BigInteger.valueOf (a) .gcd (BigInteger.valueOf (b)). er lig med (BigInteger.ONE); } 5. Konklusion
I denne hurtige vejledning har vi præsenteret en løsning på problemet med at finde ud af, om to tal er relativt primære ved hjælp af tre implementeringer af gcd algoritme.
Og som altid er prøvekoden tilgængelig på GitHub.
