Programme Java pour calculer le PGCD de deux nombres

Java

PGCD (plus grand diviseur commun) également connu sous le nom de HCF (facteur commun le plus élevé) de deux entiers ou plus est le plus grand nombre positif qui divise exactement chaque entier d'entrée.

En Java, GCD ou HCF peuvent être calculés à l'aide des méthodes suivantes :

Utiliser la boucle For
Utiliser la récursivité
Utilisation de la fonction de bibliothèque
Utilisation de l'algorithme d'Euclide
Utiliser une fonction personnalisée

Dans ce didacticiel, vous apprendrez à calculer GCD ou HCF en Java à l'aide de la boucle for, de la méthode de récursivité, de la fonction de bibliothèque Java, de l'algorithme euclidien et de la fonction personnalisée.

Programme pour calculer PGCD ou HCF de deux entiers

1) Utilisation de la boucle For et de l'instruction If

//Java program to find GCD using For Loop and If Statement

//Importing the Scanner class of Util Library of java
import java.util.Scanner;

//Main Class of the program
public class Main
{
  //Main method of the program
    public static void main(String[] args) {
      //Creating the object of Scanner Class
        Scanner input = new Scanner(System.in);
        //Asking Input from user
        System.out.print("Enter first number : ");
        //Taking input from user
        int firstNumber = input.nextInt();
        //Asking Input from user
        System.out.print("Enter second number : ");
        //Taking input from user
        int secondNumber = input.nextInt();
        //Declaring and initializing the variables
        int gcd = 1,i;

        //For Loop for iteration to find the GCF of both program
        for(i = 1; i <= firstNumber && i <= secondNumber; i++){
         /*Checking the modulation with both numbers against
           Iteration values
         */
         if(firstNumber % i == 0 && secondNumber % i == 0){
           //Replacing the gcd value with the higher Iteration value
           gcd = i;
         }
        }

        //Printing the output
        System.out.printf("GCD for %d and %d is %d",firstNumber,secondNumber,gcd);

    }
}

Sortie :

Enter first number : 88
Enter second number : 80
GCD for 88 and 80 is 8

2) Utiliser la récursivité

//Java program to find GCD using Recursion

//Importing the Scanner class of Util Library of java
import java.util.Scanner;

//Main Class of the program
public class Main
{
    //Main method of the program
    public static void main(String[] args) {
        //Creating the object of Scanner Class
        Scanner input = new Scanner(System.in);
        //Asking Input from user
        System.out.print("Enter first number : ");
        //Taking input from user
        int firstNumber = input.nextInt();
        //Asking Input from user
        System.out.print("Enter second number : ");
        //Taking input from user
        int secondNumber = input.nextInt();
        /*************
        * Declaring and Initilizing a intiger type variable to
        * capture the returned value of custom function
        **************/
        int gcd = getGCD(firstNumber, secondNumber);
        //Printing the GCD for the input values
        System.out.printf("GCD of %d , %d is %d",firstNumber,secondNumber,gcd);
    }
    //Crearting a custom function
    public static int getGCD(int number1, int number2){
      //Checking the second number is not equals to 0
      if(number2 != 0)
          //If yes,call the function inside the function{Recursion}
        return getGCD(number2, number1 % number2);
      else
          //If false, return the number1
        return number1;
    }
}

SORTIE :

Enter first number : 96
Enter second number : 88
GCD of 96, 88 is 8

3) Utilisation de la fonction de bibliothèque

//Java program to find GCD using Library Function

//Importing the Scanner class of Util Library of java
import java.util.Scanner;
//Importing the math class of java
import java.math.*;

//Main Class of the program
public class Main
{
    //Main method of the program
    public static void main(String[] args) {
        //Creating the object of Scanner Class
        Scanner input = new Scanner(System.in);
         //Asking Input from user
        System.out.print("Enter first number : ");
        //Taking input from user and storing it into Biginteger type variable
        BigInteger firstNumber = input.nextBigInteger();
         //Asking Input from user
        System.out.print("Enter second number : ");
        //Taking input from user and storing it into Biginteger type variable
        BigInteger secondNumber = input.nextBigInteger();
        //Geting the GCD of numbers using inbuild function of math library called gcd()
        BigInteger gcd = firstNumber.gcd(secondNumber);
        //Printing the output
        System.out.printf("GCD of %d , %d is %d",firstNumber,secondNumber,gcd);
    }
}

SORTIE :

Enter first number : 96
Enter second number : 80
GCD of 96 , 80 is 16

4) Utilisation de l'algorithme euclidien

//Java program to find GCD using Euclidean Algorithm

//Importing the Scanner class of Util Library of java
import java.util.Scanner;

//Main Class of the program
public class Main
{
    //Custom Function
  public static int getGCD(int firstNum, int secondNum, int firstCoff, int secondCoff){

    if(firstNum == 0){
      firstCoff = 0;
      secondCoff = 0;
      return secondNum;
    }
    //To store results of recrsive function call
    int coff1 = 1, coff2 = 1;
    //Recursive call
    int gcd = getGCD(secondNum % firstNum, firstNum, coff1, coff2);
    //Updating the coff variables for recursive call
    firstCoff = coff2 - (secondNum / firstNum) * coff1;
    secondCoff = coff1;
    //Retun the GCD
    return gcd;

  }
    //Main method of the program
    public static void main(String[] args) {
        //Creating the object of Scanner Class
        Scanner input = new Scanner(System.in);
        //Asking Input from user
        System.out.print("Enter first number : ");
        //Taking input from user
        int firstNumber = input.nextInt();
         //Asking Input from user
        System.out.print("Enter second number : ");
        //Asking Input from user
        int secondNumber = input.nextInt();
        int x = 1, y = 1;
        /*************
        * Declaring and Initilizing a intiger type variable to
        * capture the returned value of custom function
        **************/
        int gcd = getGCD(firstNumber, secondNumber, x, y);
        //Printing the output
        System.out.printf("GCD of %d , %d is %d",firstNumber,secondNumber,gcd);

    }
}

SORTIE :

Enter first number : 96
Enter second number : 80
GCD of 96 , 80 is 16

5) Utilisation de la fonction personnalisée

//Java program to find GCD using Custom Function

//Importing the Scanner class of Util Library of java
import java.util.Scanner;

//Main Class of the program
public class Main
{
  //Custom Function
  public static int getGCD(int firstNum, int secondNum){
    //Integer type variable
    int gcd = 1, i;
    //For loop for iteration
    for(i = 1; i <= firstNum && i <= secondNum; ++i){
      //Checking the modulation of both numbers with iteration
      //value is equals to 0
      if(firstNum % i == 0 && secondNum % i == 0){
        //if yes,Update the gcd variable value with iteration value
        gcd = i;
      }
    }
    //Returing the gcd;
    return gcd;
  }
  //Main method of the program
    public static void main(String[] args) {
      //Creating the object of Scanner Class
        Scanner input = new Scanner(System.in);
         //Asking Input from user
        System.out.print("Enter first number : ");
        //Taking input from user
        int firstNumber = input.nextInt();
         //Asking Input from user
        System.out.print("Enter second number : ");
        //Taking input from user
        int secondNumber = input.nextInt();
        //Taking the returned value from getGCD Custom Function
        int gcd = getGCD(firstNumber,secondNumber);
        //Printing the output
        System.out.printf("GCD of %d , %d is %d",firstNumber,secondNumber,gcd);
    }
}

Sortie :

Enter first number : 80
Enter second number : 96
GCD of 80 , 96 is 16