Java >> Tutoriel Java >  >> Java

PGCD de N nombres en Java

Java

PGCD de N Nombres en Java | Programmes de tableaux en Java – 17 | Dans le programme Java précédent, nous avons développé des programmes pour trier les éléments d'un tableau et trouver l'inverse d'un tableau.

Description du programme :- Écrivez un programme Java pour trouver le PGCD de N nombres ou de plus de deux nombres. Le PGCD de trois nombres ou plus peut être calculé en prenant à plusieurs reprises le PGCD de paires de nombres.

gcd(a, b, c) = gcd(a, gcd(b, c)) = gcd(gcd(a, b), c) = gcd(gcd(a, c), b)

Le PGCD de N nombres se calcule également en trouvant les facteurs premiers, le PGCD de N nombres est égal aux facteurs premiers communs à tous les nombres.

Pour un tableau de nombres, le PGCD peut être calculé comme ,

// initialize result with first number in the array
result = arr[0];
// loop
for i = 1 to n-1
result = findHCF(result, arr[i])

Procédure pour trouver GCD ou HCF de deux nombres ,

1) Prenez deux nombres
2) Trouvez le plus grand et le plus petit nombre parmi eux
3) Soustrayez la plus petite valeur numérique du plus grand nombre
4) Répétez ce processus jusqu'à ce que les deux nombres deviennent égaux

Le GCD ou HCF de deux nombres en Java peut être calculé comme ,

// Java method to find GCD or HCF of two numbers
public static int findHCF(int num1, int num2) {
  while(num1 != num2) {
    if(num1 > num2) 
       num1 = num1 - num2;
    else
       num2 = num2 - num1;
  }
  return num1;
}

Programme Java pour trouver le PGCD de N nombres

public class GCD {
  public static void main(String[] args) {

    // variables
    int size = 0;
    int arr[] = null;
    int result = 0;
    
    // create Scanner class object to read input
    Scanner scan = new Scanner(System.in);
    
    // read size
    System.out.print("Enter total numbers: ");
    size = scan.nextInt();
    
    // declare array
    arr = new int[size];
    
    // read numbers
    System.out.println("Enter numbers: ");
    for(int i=0; i<size; i++) {
      arr[i] = scan.nextInt();
    }
    
    // assign first number to result
    result = arr[0];
    
    // loop
    for(int i=1; i<size; i++) {
      result = findHCF(result, arr[i]);
    }
    
    // display result
    System.out.println("GCD = " + result);

    // close Scanner
    scan.close();
  }

  // recursive method
  public static int findHCF(int num1, int num2) {
    while (num1 != num2) {
      if (num1 > num2)
        num1 = num1 - num2;
      else
        num2 = num2 - num1;
    }
    return num1;
  }
}

Sortie pour les différents cas de test :-

Entrez le nombre total :3
Entrez le nombre :
10 15 25
GCD =5

Entrez le nombre total :5
Entrez le nombre :
9 36 25 5 12
GCD =1

Dans ce programme, nous avons d'abord pris les variables requises :- taille, arr et résultat. La variable size contiendra le nombre d'éléments dans le tableau, la variable arr représente le tableau et la variable result contiendra le résultat final.

Ensuite, nous avons créé un objet de la classe Scanner pour lire les valeurs d'entrée de l'utilisateur final. Pour lire les entrées de l'utilisateur final, vous pouvez également utiliser la classe BufferedReader. La taille du tableau doit être prise avant de déclarer le tableau. Après avoir déclaré le tableau, prenez des nombres, c'est-à-dire des éléments du tableau. Le premier numéro sera attribué à la variable de résultat. Maintenant, utilisez la boucle pour répéter le processus et calculez le résultat en prenant à plusieurs reprises le PGCD de paires de nombres.


Balise Java