Java-program til at beregne GCD af to tal

Java

GCD (Greatest Common Divisor) også kendt som HCF (Highest Common Factor) af to eller flere heltal er det største positive tal, som nøjagtigt deler hvert eneste input-heltal.

I Java kan GCD eller HCF beregnes ved hjælp af følgende metoder:

Brug af For Loop
Brug af rekursion
Brug af biblioteksfunktion
Brug af den euklidiske algoritme
Brug af en brugerdefineret funktion

I denne øvelse lærer du, hvordan du beregner GCD eller HCF i Java ved hjælp af for loop, rekursionsmetode, Java-biblioteksfunktion, Euklidisk algoritme og brugerdefineret funktion.

Program til at beregne GCD eller HCF af to heltal

1) Brug af For Loop og If-erklæring

//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);

    }
}

Output:

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

2) Brug af rekursion

//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;
    }
}

OUTPUT:

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

3) Brug af biblioteksfunktion

//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);
    }
}

OUTPUT:

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

4) Brug af den euklidiske algoritme

//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);

    }
}

OUTPUT:

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

5) Brug af brugerdefineret funktion

//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);
    }
}

Output:

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