streamalism.org

1. Overzicht

Gegeven twee gehele getallen, een en b, we zeggen dat ze zijn relatief priem als de enige factor die beide verdeelt 1 is. Onderling priemgetallen of coprime zijn synoniemen voor relatief priemgetallen.

In deze korte tutorial zullen we een oplossing voor dit probleem doornemen met behulp van Java.

2. Grootste gemeenschappelijke factor-algoritme

Het blijkt dat als de grootste gemene deler (gcd) van 2 nummers een en b is 1 (d.w.z. ggd (a, b) = 1) dan een en b zijn relatief prime. Het resultaat is dat het bepalen of twee getallen relatief priem zijn eenvoudigweg uitzoeken of de gcd is 1.

3. Euclidische algoritme implementatie

In deze sectie gebruiken we het Euclidische algoritme om de gcd van 2 nummers.

Laten we, voordat we onze implementatie laten zien, het algoritme samenvatten en ter wille van het begrip een snel voorbeeld bekijken van hoe het toe te passen.

Stel je voor dat we twee gehele getallen hebben, een en b. Bij de iteratieve benadering delen we eerst een door b en ontvang de rest. Vervolgens wijzen we toe een de waarde van b, en we wijzen b de restwaarde. We herhalen dit proces tot b = 0. Ten slotte, wanneer we dit punt bereiken, retourneren we de waarde van een als de gcd resultaat, en als een = 1, we kunnen stellen dat een en b zijn relatief prime.

Laten we het uitproberen op twee gehele getallen, a = 81 en b = 35.

In dit geval is de rest van 81 en 35 (81 % 35) is 11. Dus in de eerste iteratiestap eindigen we met a = 35 en b = 11. Daarom doen we nog een iteratie.

De rest van 35 gedeeld door 11 is 2. Als resultaat hebben we nu a = 11 (we hebben waarden geruild) en b = 2. Laten we door gaan.

Nog een stap zal resulteren in a = 2 en b = 1. Nu komen we dicht bij het einde.

Ten slotte, na nog een iteratie, zullen we bereiken a = 1 en b = 0. Het algoritme keert terug 1 en dat kunnen we concluderen 81 en 35 zijn inderdaad relatief priem.

3.1. Imperatieve implementatie

Laten we eerst de imperatieve Java-versie van het Euclidische algoritme implementeren zoals hierboven beschreven:

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; } retourneer een; } 

Zoals we kunnen zien, in het geval waar een is minder dan b, wisselen we de waarden uit voordat we verder gaan. Het algoritme stopt wanneer b is 0.

3.2. Recursieve implementatie

Laten we vervolgens eens kijken naar een recursieve implementatie. Dit is waarschijnlijk schoner omdat het expliciete wisselingen van variabele waarden vermijdt:

int recursiveGCD (int a, int b) {if (b == 0) {return a; } if (a <b) {retourneer recursieveGCD (b, a); } retourneer recursieveGCD (b, a% b); } 

4. Met behulp van BigIntegerImplementatie

Maar wacht - is het niet gcd algoritme al geïmplementeerd in Java? Jawel! De BigInteger klasse biedt een gcd methode die het Euclidische algoritme implementeert voor het vinden van de grootste gemene deler.

Met behulp van deze methode kunnen we gemakkelijker het relatief primaire algoritme opstellen als:

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

5. Conclusie

In deze korte tutorial hebben we een oplossing gepresenteerd voor het probleem om te achterhalen of twee getallen relatief priem zijn met behulp van drie implementaties van de gcd algoritme.

En, zoals altijd, is de voorbeeldcode beschikbaar op GitHub.