Java >> Java tutorial >  >> Java

Java-program til at beregne GCD

Java

I den forrige artikel har vi set Java-program til at finde rødderne til kvadratisk ligning

I denne artikel skal vi se, hvordan du finder GCD'en ved hjælp af Java-programmeringssproget.

Java-program til beregning af GCD

Før du hopper direkte ind i programmet, lad os vide, hvad denne GCD er.

Største fælles deler:

Største fælles divisor (GCD) også kendt som den største fælles faktor (GCF) eller højeste fælles faktor (HCF) af to heltal 'a' og 'b' er defineret til at være det største heltal, der deler både 'a' og 'b' uden rest.

Eksempler: 

Let a and b are two numbers. a = 20 b = 30 Common factors of (20,30) = 1, 2, 5, 10 So, GCD = 10

Lad os se forskellige måder at finde GCD'en på.

  • Generel tilgang med statiske inputværdier
  • Generel tilgang med brugerinputværdier
  • Ved at bruge euklidisk gentagen subtraktionsmetode

Metode-1:Java-program til at beregne GCD ved at bruge generel tilgang med statiske inputværdier

Fremgangsmåde:

  • Erklær en int-variabel siger ‘a’ og tildel værdien til den, som holder værdien af ​​det første tal.
  • Deklarer en dobbelt variabel siger ‘b’ og tildel værdien til den, som holder værdien af ​​det andet tal.
  • Deklarer en int-variabel siger ‘GCD’ og initialiser den til 1.
  • Tag derefter en for-løkke startende fra i=1 to i=n hvor n er det mindste tal mellem ‘a’ og ‘b’ .
  • Tjek største heltal, der deler begge a og b uden rester og udskriv resultatet.

Program: 

import java.io.*;
public class Main
{
    public static void main(String [] args)
    {
        //Two numbers are declared
        int a = 20;
        int b = 10;
        //integer variable GCD declared to hold GCD value
        //also initualized to 1
        int GCD =  1; 
        
        //checking the smaller number between a and b
        //and assigning the smaller number to variable n
        int n=0;
        if(a<b)
            n=a;
        else
            n=b;
    
        //Here i is the factor of n
        //since the 1st factor of any number is 1. Hence we have initialized it to 1.
        //loop will go upto 'n' which holds the smaller number between 'a' and 'b'
        for(int i = 1; i<=n; i++) 
        {
            //Checking largest integer that divides both a and b with no remainder
        	if(a%i == 0 && b%i==0)
        		GCD = i;
        }
        System.out.println("The GCD of ("+ a + "," + b + ") is: " + GCD);
    }
}

Output:

The GCD of (20,10) is: 10

Metode-2:Java-program til at beregne GCD ved at bruge generel tilgang med brugerinputværdier

Fremgangsmåde:

  • Deklarer en int-variabel siger ‘a’ som indeholder værdien af ​​det første tal.
  • Deklarer en dobbelt variabel, sig ‘b’ som indeholder værdien af ​​det andet tal.
  • Tag værdien a og b som brugerinput ved at bruge Scanner-klassen.
  • Erklær en int-variabel, sig ‘GCD’ og initialiser den til 1.
  • Så tag en for-løkke startende fra i=1 to i=n hvor n er det mindste tal mellem ‘a’ og ‘b’ .
  • Tjek største heltal, der deler begge a og b uden rester og udskriv resultatet.

Program: 

import java.util.*;
public class Main
{
    public static void main(String [] args)
    {
        Scanner sc=new Scanner(System.in);
        //taking input of two numbers from user
        System.out.println("Enter two numbers:");
        int a = sc.nextInt();
        int b = sc.nextInt();
        //integer variable GCD declared to hold GCD value
        //also initualized to 1
        int GCD =  1; 
        
        //checking the smaller number between a and b
        //and assigning the smaller number to variable n
        int n=0;
        if(a<b)
            n=a;
        else
            n=b;
    
        //Here i is the factor of n
        //since the 1st factor of any number is 1. Hence we have initialized it to 1.
        //loop will go upto 'n' which holds the smaller number between 'a' and 'b'
        for(int i = 1; i<=n; i++) 
        {
            //Checking largest integer that divides both a and b with no remainder
        	if(a%i == 0 && b%i==0)
        		GCD = i;
        }
        System.out.println("The GCD of ("+ a + "," + b + ") is: " + GCD);
    }
}

Output:

Enter two numbers:
10
20
The GCD of (10,20) is: 10

Metode-3:Java-program til at beregne GCD ved at bruge euklidisk gentagen subtraktionsmetode

Fremgangsmåde:

  • Erklær en int-variabel, sig ‘a’ og tildel værdien til den, som holder værdien af ​​det første tal.
  • Deklarer en dobbelt variabel siger ‘b’ og tildel værdien til den, som holder værdien af ​​det andet tal.
  • Deklarer en int-variabel siger ‘GCD’ og initialiser den til 1.
  • Så finder vi GCD'en ved hjælp af euklidisk gentagen subtraktion.
  • Udskriv resultatet.

Program: 

public class Main
{
public static int GCD(int a, int b)
    {
        if (b == 0)
            return a;
        // here the GCD() method is called recursively 
        // by replacing a with b, and b with (a-b)  till b != 0
        else
            return GCD(b, a - b);
    }
    
    public static void main(String [] args)
    {
        int a = 20;
        int b = 10; 
        System.out.println("GCD = " + GCD(a, b));
    }

}

Output: GCD = 10

Den medfølgende liste over Simple Java-programmer er specielt designet til nybegyndere og begyndere for at blive fortrolige med begreberne Java-programmeringssprog og blive pro i kodning.

Relaterede Java-programmer:

  • Java-program til at finde LCM af to numre ved hjælp af Euclids algoritme
  • Java-program til at konvertere en vinkel i radianer til grader
  • Java-program til at konvertere en vinkel i grader til radianer
  • Java-program til at finde kuberod af et tal

Java tag