Trova se due numeri sono relativamente primi in Java

1. Panoramica

Dati due numeri interi, una e B , diciamo che sono relativamente primi se l'unico fattore che divide entrambi è 1. Reciprocamente primo o coprimi sono sinonimi di numeri relativamente primi.

In questo rapido tutorial, illustreremo una soluzione a questo problema utilizzando Java.

2. Algoritmo del più grande fattore comune

Come si è visto, se il massimo comun divisore ( gcd ) di 2 numeri a e b è 1 (cioè gcd (a, b) = 1 ) allora un e b sono primi. Di conseguenza, determinare se due numeri sono relativamente primi consiste semplicemente nel trovare se il mcd è 1.

3. Implementazione dell'algoritmo euclideo

In questa sezione utilizzeremo l'algoritmo euclideo per calcolare il mcd di 2 numeri.

Prima di mostrare la nostra implementazione, riassumiamo l'algoritmo e guardiamo un rapido esempio di come applicarlo per motivi di comprensione.

Quindi, immagina di avere due numeri interi, a e b . Nell'approccio iterativo, prima dividiamo a per be otteniamo il resto. Successivamente, assegniamo a il valore di b e assegniamo a b il valore rimanente. Ripetiamo questo processo fino a quando b = 0 . Infine, quando si raggiunge questo punto, si ritorna al valore di una come gcd risultato, e se un = 1 , possiamo dire che un e b sono primi.

Proviamo su due numeri interi, a = 81 e b = 35 .

In questo caso, il resto di 81 e 35 (81% 35) è 11 . Così, nel primo passo di iterazione, si finisce con a = 35 e b = 11 . Di conseguenza, faremo un'altra iterazione.

Il resto di 35 diviso 11 è 2 . Di conseguenza, ora abbiamo a = 11 (abbiamo scambiato i valori) eb = 2 . Andiamo avanti.

Un altro passo comporterà a = 2 e b = 1 . Adesso ci stiamo avvicinando alla fine.

Infine, dopo un altro iterazione, arriveremo a = 1 e b = 0 . L'algoritmo restituisce 1 e possiamo concludere che 81 e 35 sono effettivamente primi tra loro.

3.1. Implementazione imperativa

Innanzitutto, implementiamo la versione Java imperativa dell'algoritmo euclideo come descritto sopra:

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; } return a; } 

Come possiamo notare, nel caso in cui a è minore di b , scambiamo i valori prima di continuare. L'algoritmo si ferma quando b è 0.

3.2. Implementazione ricorsiva

Successivamente, diamo un'occhiata a un'implementazione ricorsiva. Questo è probabilmente più pulito poiché evita scambi di valori variabili espliciti:

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

4. Utilizzo dell'implementazione di BigInteger

Ma aspetta: l' algoritmo gcd non è già implementato in Java? Sì! La classe BigInteger fornisce un metodo gcd che implementa l'algoritmo euclideo per trovare il massimo comune divisore.

Usando questo metodo, possiamo disegnare più facilmente l'algoritmo relativamente primo come:

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

5. conclusione

In questo rapido tutorial, abbiamo presentato una soluzione al problema di trovare se due numeri sono relativamente primi utilizzando tre implementazioni dell'algoritmo gcd .

E, come sempre, il codice di esempio è disponibile su GitHub.