Trovare il miglior divisore comune in Java

1. Panoramica

In matematica, il GCD di due numeri interi, che sono diversi da zero, è il più grande numero intero positivo che divide ciascuno degli interi in modo uniforme.

In questo tutorial, esamineremo tre approcci per trovare il Greatest Common Divisor (GCD) di due numeri interi. Inoltre, esamineremo la loro implementazione in Java.

2. Forza bruta

Per il nostro primo approccio, iteriamo da 1 al numero più piccolo dato e controlliamo se gli interi dati sono divisibili per l'indice. L'indice più grande che divide i numeri dati è il GCD dei numeri dati:

int gcdByBruteForce(int n1, int n2) { int gcd = 1; for (int i = 1; i <= n1 && i <= n2; i++) { if (n1 % i == 0 && n2 % i == 0) { gcd = i; } } return gcd; }

Come possiamo vedere, la complessità dell'implementazione sopra è O (min (n1, n2)) perché dobbiamo iterare sul ciclo per n volte (equivalente al numero più piccolo) per trovare il GCD.

3. Algoritmo di Euclide

Secondo, possiamo usare l'algoritmo di Euclide per trovare il GCD. L'algoritmo di Euclide non è solo efficiente, ma anche facile da capire e da implementare utilizzando la ricorsione in Java.

Il metodo di Euclide dipende da due importanti teoremi:

  • Innanzitutto, se sottraiamo il numero più piccolo dal numero più grande, il MCD non cambia, quindi, se continuiamo a sottrarre il numero, alla fine finiamo con il loro MCD
  • Secondo, quando il numero più piccolo divide esattamente il numero più grande, il numero più piccolo è il GCD dei due numeri dati.

Nota nella nostra implementazione che useremo il modulo invece della sottrazione poiché è fondamentalmente molte sottrazioni alla volta:

int gcdByEuclidsAlgorithm(int n1, int n2) { if (n2 == 0) { return n1; } return gcdByEuclidsAlgorithm(n2, n1 % n2); }

Inoltre, nota come usiamo n2 nella posizione di n1 e usiamo il resto nella posizione di n2 nel passo ricorsivo dell'algoritmo .

Inoltre, la complessità dell'algoritmo di Euclide è O (Log min (n1, n2)) che è migliore rispetto al metodo Brute Force che abbiamo visto prima.

4. Algoritmo di Stein o algoritmo GCD binario

Infine, possiamo utilizzare l'algoritmo di Stein, noto anche come algoritmo Binary GCD , per trovare il GCD di due interi non negativi. Questo algoritmo utilizza semplici operazioni aritmetiche come spostamenti aritmetici, confronto e sottrazione.

L'algoritmo di Stein applica ripetutamente le seguenti identità di base relative ai GCD per trovare GCD di due numeri interi non negativi:

  1. mcd (0, 0) = 0, mcd (n1, 0) = n1, mcd (0, n2) = n2
  2. Quando n1 e n2 sono entrambi numeri interi pari, allora mcd (n1, n2) = 2 * mcd (n1 / 2, n2 / 2) , poiché 2 è il divisore comune
  3. Se n1 è un numero intero pari e n2 è un numero intero dispari, allora mcd (n1, n2) = mcd (n1 / 2, n2) , poiché 2 non è il divisore comune e viceversa
  4. Se n1 e n2 sono entrambi numeri interi dispari e n1> = n2 , allora gcd (n1, n2) = mcd ((n1-n2) / 2, n2) e viceversa

Ripetiamo i passaggi 2-4 finché n1 è uguale a n2 o n1 = 0 . Il GCD è (2n) * n2 . Qui, n è il numero di volte in cui 2 è comune in n1 e n2 durante l'esecuzione del passaggio 2:

int gcdBySteinsAlgorithm(int n1, int n2) { if (n1 == 0) { return n2; } if (n2 == 0) { return n1; } int n; for (n = 0; ((n1 | n2) & 1) == 0; n++) { n1 >>= 1; n2 >>= 1; } while ((n1 & 1) == 0) { n1 >>= 1; } do { while ((n2 & 1) == 0) { n2 >>= 1; } if (n1 > n2) { int temp = n1; n1 = n2; n2 = temp; } n2 = (n2 - n1); } while (n2 != 0); return n1 << n; }

Possiamo vedere che usiamo operazioni di spostamento aritmetiche per dividere o moltiplicare per 2. Inoltre, usiamo la sottrazione per ridurre i numeri dati.

La complessità dell'algoritmo di Stein quando n1> n2 è O ((log 2 n1) 2) mentre. quando n1 <n2, è O ((log 2 n2) 2).

5. conclusione

In questo tutorial, abbiamo esaminato vari metodi per calcolare il GCD di due numeri. Li abbiamo anche implementati in Java e abbiamo esaminato rapidamente la loro complessità.

Come sempre, il codice sorgente completo dei nostri esempi qui è, come sempre, su GitHub.