Come scrivere un semplice programma Java che trova il massimo comun divisore tra due numeri?

Question

ecco la domanda:.

"Scrivi un metodo chiamato GCD che accetta due interi come parametri e restituisce il massimo comune divisore di due numeri il massimo comune divisore (MCD) di due numeri interi A e B è il più grande intero che è un fattore di entrambi a e B. Il GCD di qualsiasi numero e 1 è 1 e il GCD di qualsiasi numero e 0 è quel numero

Un modo efficiente per calcolare il GCD di due numeri è quello di utilizzare Algoritmo di Euclide, che afferma quanto segue:

GCD(A, B) = GCD(B, A % B) 
GCD(A, 0) = Absolute value of A" 

Sono davvero confuso da w per risolvere questo problema. Voglio solo alcuni suggerimenti e suggerimenti su cosa ho fatto di sbagliato nel programma che ho finora. (Devo inserire uno scanner, questa è la mia esigenza dell'insegnante.) Non darmi un codice completo perché voglio risolverlo da solo. Forse dammi solo un suggerimento su come incorporare questa formula che vedi sopra. (E se ti stai chiedendo perché ho inserito il valore == 0, è perché pensavo che se hai due numeri, diciamo 0 e 90, il loro GCD sarebbe 0 giusto ??)

Inoltre, il mio codice ha per includere cicli while ... Avrei preferito se i loop ...

Grazie in anticipo! :)

mio programma in corso:

public static void main(String[] args) { 
     Scanner console = new Scanner(System.in); 
     int a = console.nextInt(); 
     int b = console.nextInt(); 
     gcd (a, b); 
    } 

    public static void gcd(int a, int b) { 
     System.out.print("Type in two numbers and I will print outs its Greatest Common Divisor: "); 
     int gcdNum1 = console.nextInt(); 
     int gcdNum2 = console.nextInt(); 
     while (gcdNum1 == 0) { 
      gcdNum1 = 0; 
     } 
     while (gcdNum2 > gcdNum1) { 
      int gcd = gcdNum1 % gcdNum2; 
     } 
     System.out.print(gcdNum1 + gcdNum2); 
    } 
} 

Answer 1

Un metodo ricorsivo potrebbe essere:

static int gcd(int a, int b) 
{ 
    if(a == 0 || b == 0) return a+b; // base case 
    return gcd(b,a%b); 
} 

Utilizzando un ciclo while:

static int gcd(int a, int b) 
{ 
    while(a!=0 && b!=0) // until either one of them is 0 
    { 
    int c = b; 
    b = a%b; 
    a = c; 
    } 
    return a+b; // either one is 0, so return the non-zero value 
} 

quando sto tornando a+b, ho restituisco effettivamente il numero diverso da zero assumendo che uno di essi sia 0.

Answer 2

Un modo per farlo è il codice qui sotto:

 int gcd = 0; 
     while (gcdNum2 !=0 && gcdNum1 != 0) { 
     if(gcdNum1 % gcdNum2 == 0){ 
      gcd = gcdNum2; 
     } 
      int aux = gcdNum2; 
      gcdNum2 = gcdNum1 % gcdNum2; 
      gcdNum1 = aux; 
    } 

Non è necessario ricorsione di fare questo.

E fai attenzione, dice che quando un numero è zero, allora il GCD è il numero che non è zero.

while (gcdNum1 == 0) { 
    gcdNum1 = 0; 
} 

È necessario modificare questo per soddisfare il requisito.

Non ho intenzione di dirvi come modificare completamente il codice, solo come calcolare il gcd.

Answer 3

import java.util.Scanner; 


public class Main { 




public static void main(String [] args) 
{ 
    Scanner input = new Scanner(System.in); 
    System.out.println("Please enter the first integer:"); 
    int b = input.nextInt(); 
    System.out.println("Please enter the second integer:"); 
    int d = input.nextInt(); 

    System.out.println("The GCD of " + b + " and " + d + " is " + getGcd(b,d) + "."); 
} 


public static int getGcd(int b, int d) 
{ 
    int gcd = 1; 

    if(b>d) 
    { 
     for(int i = d; i >=1; i--) 
     { 
      if(b%i==0 && d%i ==0) 
      { 
       return i; 
      } 
     } 
    } 
    else 
    { 
     for(int j = b; j >=1; j--) 
     { 
      if(b%j==0 && d% j==0) 
      { 
       return j; 
      } 
     } 
    } 
    return gcd; 

} 
} 

Answer 4

private static void GCD(int a, int b) { 

    int temp; 
    // make a greater than b 
    if (b > a) { 
     temp = a; 
     a = b; 
     b = temp; 
    } 

    while (b !=0) { 
     // gcd of b and a%b 
     temp = a%b; 
     // always make a greater than bf 
     a =b; 
     b =temp; 

    } 
    System.out.println(a); 
} 

Answer 5

public static int GCD(int x, int y) { 
    int r; 
    while (y!=0) { 
     r = x%y; 
     x = y; 
     y = r; 
    } 
    return x; 
} 

Answer 6

Si può anche farlo in un metodo di tre linee:

public static int gcd(int x, int y){ 
    return (y == 0) ? x : gcd(y, x % y); 
} 

Qui, se y = 0, x viene restituito. In caso contrario, viene richiamato il metodo gcd, con valori di parametro diversi.

Answer 7

import java.util.Scanner; 

class CalculateGCD 
{ 
    public static int calGCD(int a, int b) 
    { 
    int c=0,d=0; 
    if(a>b){c=b;} 
    else{c=a;} 
    for(int i=c; i>0; i--) 
    { 
    if(((a%i)+(b%i))==0) 
    { 
    d=i; 
    break; 
    } 
    } 
    return d; 
    } 

    public static void main(String args[]) 
    { 
    Scanner sc=new Scanner(System.in); 
    System.out.println("Enter the nos whose GCD is to be calculated:"); 
    int a=sc.nextInt(); 
    int b=sc.nextInt(); 
    System.out.println(calGCD(a,b)); 
    } 
} 

Answer 8

Ora, ho appena iniziato a programmare circa una settimana fa, quindi niente di speciale, ma ho avuto questo come un problema e si avvicinò con questo, che può essere più facile per le persone che sono solo entrare in programmazione da capire. Usa il metodo di Euclide come negli esempi precedenti.

public class GCD { 
    public static void main(String[] args){ 
    int x = Math.max(Integer.parseInt(args[0]),Integer.parseInt(args[1]));  
    int y = Math.min(Integer.parseInt(args[0]),Integer.parseInt(args[1]));  
    for (int r = x % y; r != 0; r = x % y){ 
     x = y; 
     y = r; 
    } 
    System.out.println(y); 
    } 
}