sacar - programa en java para calcular el mcd

Java: obtener el mayor divisor común

Question

He visto que existe una función de este tipo para BigInteger , es decir, BigInteger#gcd . ¿Hay otras funciones en Java que también funcionen para otros tipos ( int , long o Integer )? Parece que esto tendría sentido como java.lang.Math.gcd (con todo tipo de sobrecargas) pero no está allí. ¿Es en otro lado?

(No confunda esta pregunta con "cómo lo implemento yo mismo", ¡por favor!)

Answer 1

¿Es en otro lado?

Apache! - Tiene tanto gcd como lcm, ¡genial!

Answer 2

A menos que tenga guayaba, defino así:

int gcd(int a, int b) {
  return a == 0 ? b : gcd(b % a, a);
}

Answer 3

Algunas implementaciones aquí no funcionan correctamente si ambos números son negativos. gcd (-12, -18) es 6, no -6.

Entonces, debe devolverse un valor absoluto, algo así como

public static int gcd(int a, int b) {
    if (b == 0) {
        return Math.abs(a);
    }
    return gcd(b, a % b);
}

Answer 4

El% va a darnos el gcd Entre dos números, significa: -% o mod de big_number / small_number son = gcd, y lo escribimos en java como este big_number % small_number .

EX1: para dos enteros

  public static int gcd(int x1,int x2)
    {
        if(x1>x2)
        {
           if(x2!=0)
           {
               if(x1%x2==0)     
                   return x2;
                   return x1%x2;
                   }
           return x1;
           }
          else if(x1!=0)
          {
              if(x2%x1==0)
                  return x1;
                  return x2%x1;
                  }
        return x2;
        } 

EX2: para tres enteros

public static int gcd(int x1,int x2,int x3)
{

    int m,t;
    if(x1>x2)
        t=x1;
    t=x2;
    if(t>x3)
        m=t;
    m=x3;
    for(int i=m;i>=1;i--)
    {
        if(x1%i==0 && x2%i==0 && x3%i==0)
        {
            return i;
        }
    }
    return 1;
}

Answer 5

Hasta donde yo sé, no hay ningún método incorporado para primitivos. Pero algo tan simple como esto debería hacer el truco:

public int GCD(int a, int b) {
   if (b==0) return a;
   return GCD(b,a%b);
}

También puede alinearlo si le gusta ese tipo de cosas:

public int GCD(int a, int b) { return b==0 ? a : GCD(b, a%b); }

Cabe señalar que no hay absolutamente ninguna diferencia entre los dos, ya que compilan con el mismo código de bytes.

Answer 6

Jakarta Commons Math tiene exactamente eso.

ArithmeticUtils.gcd (int p, int q)

Answer 7

O el algoritmo euclidiano para calcular el GCD ...

public int egcd(int a, int b) {
    if (a == 0)
        return b;

    while (b != 0) {
        if (a > b)
            a = a - b;
        else
            b = b - a;
    }

    return a;
}

Answer 8

Para int y largo, como primitivos, no realmente. Para Integer, es posible que alguien haya escrito uno.

Dado que BigInteger es un superconjunto (matemático / funcional) de int, Integer, long y Long, si necesita usar estos tipos, conviértalos a BigInteger, haga el GCD y convierta el resultado.

private static int gcdThing(int a, int b) {
    BigInteger b1 = new BigInteger(""+a); // there''s a better way to do this. I forget.
    BigInteger b2 = new BigInteger(""+b);
    BigInteger gcd = b1.gcd(b2);
    return gcd.intValue();
}

La mejor manera:

private static int gcdThing(int a, int b) {
    BigInteger b1 = BigInteger.valueOf(a);
    BigInteger b2 = BigInteger.valueOf(b);
    BigInteger gcd = b1.gcd(b2);
    return gcd.intValue();
}

Answer 9

Puede usar esta implementación del algoritmo Binario GCD

public class BinaryGCD {

public static int gcd(int p, int q) {
    if (q == 0) return p;
    if (p == 0) return q;

    // p and q even
    if ((p & 1) == 0 && (q & 1) == 0) return gcd(p >> 1, q >> 1) << 1;

    // p is even, q is odd
    else if ((p & 1) == 0) return gcd(p >> 1, q);

    // p is odd, q is even
    else if ((q & 1) == 0) return gcd(p, q >> 1);

    // p and q odd, p >= q
    else if (p >= q) return gcd((p-q) >> 1, q);

    // p and q odd, p < q
    else return gcd(p, (q-p) >> 1);
}

public static void main(String[] args) {
    int p = Integer.parseInt(args[0]);
    int q = Integer.parseInt(args[1]);
    System.out.println("gcd(" + p + ", " + q + ") = " + gcd(p, q));
}

}

De http://introcs.cs.princeton.edu/java/23recursion/BinaryGCD.java.html

Answer 10

Si está utilizando Java 1.5 o posterior, este es un algoritmo iterativo GCD binario que utiliza Integer.numberOfTrailingZeros() para reducir la cantidad de comprobaciones y repeticiones requeridas.

public class Utils {
    public static final int gcd( int a, int b ){
        // Deal with the degenerate case where values are Integer.MIN_VALUE
        // since -Integer.MIN_VALUE = Integer.MAX_VALUE+1
        if ( a == Integer.MIN_VALUE )
        {
            if ( b == Integer.MIN_VALUE )
                throw new IllegalArgumentException( "gcd() is greater than Integer.MAX_VALUE" );
            return 1 << Integer.numberOfTrailingZeros( Math.abs(b) );
        }
        if ( b == Integer.MIN_VALUE )
            return 1 << Integer.numberOfTrailingZeros( Math.abs(a) );

        a = Math.abs(a);
        b = Math.abs(b);
        if ( a == 0 ) return b;
        if ( b == 0 ) return a;
        int factorsOfTwoInA = Integer.numberOfTrailingZeros(a),
            factorsOfTwoInB = Integer.numberOfTrailingZeros(b),
            commonFactorsOfTwo = Math.min(factorsOfTwoInA,factorsOfTwoInB);
        a >>= factorsOfTwoInA;
        b >>= factorsOfTwoInB;
        while(a != b){
            if ( a > b ) {
                a = (a - b);
                a >>= Integer.numberOfTrailingZeros( a );
            } else {
                b = (b - a);
                b >>= Integer.numberOfTrailingZeros( b );
            }
        }
        return a << commonFactorsOfTwo;
    }
}

Prueba de unidad:

import java.math.BigInteger;
import org.junit.Test;
import static org.junit.Assert.*;

public class UtilsTest {
    @Test
    public void gcdUpToOneThousand(){
        for ( int x = -1000; x <= 1000; ++x )
            for ( int y = -1000; y <= 1000; ++y )
            {
                int gcd = Utils.gcd(x, y);
                int expected = BigInteger.valueOf(x).gcd(BigInteger.valueOf(y)).intValue();
                assertEquals( expected, gcd );
            }
    }

    @Test
    public void gcdMinValue(){
        for ( int x = 0; x < Integer.SIZE-1; x++ ){
            int gcd = Utils.gcd(Integer.MIN_VALUE,1<<x);
            int expected = BigInteger.valueOf(Integer.MIN_VALUE).gcd(BigInteger.valueOf(1<<x)).intValue();
            assertEquals( expected, gcd );
        }
    }
}

Answer 11

Usé el siguiente método.

/**
 * @param args the command line arguments
 */
public static void main(String[] args) {

    // First number
    int n1 = 16;
    // Second number
    int n2 = 24;
    // Greatest Common Divisor
    int gdk = 0;

    for (int k = 2; k <= n1 && k <= n2; k++){
        if(n1 % k == 0 && n2 % k == 0){
            gdk = k;
        }
    }

    System.out.println(gdk);
}

Answer 12

Usé este método que creé cuando tenía 14 años.

    public static int gcd (int a, int b) {
        int s = 1;
        int ia = Math.abs(a);//<-- turns to absolute value
        int ib = Math.abs(b);
        if (a == b) {
            s = a;
        }else {
            while (ib != ia) {
                if (ib > ia) {
                    s = ib - ia;
                    ib = s;
                }else { 
                    s = ia - ib;
                    ia = s;
                }
            }
        }
        return s;
    }

Answer 13

Utilice Guava LongMath.gcd() e IntMath.gcd()

Answer 14

podemos usar la función recursiva para encontrar gcd

public class Test
{
 static int gcd(int a, int b)
    {
        // Everything divides 0 
        if (a == 0 || b == 0)
           return 0;

        // base case
        if (a == b)
            return a;

        // a is greater
        if (a > b)
            return gcd(a-b, b);
        return gcd(a, b-a);
    }

    // Driver method
    public static void main(String[] args) 
    {
        int a = 98, b = 56;
        System.out.println("GCD of " + a +" and " + b + " is " + gcd(a, b));
    }
}

Answer 15

/*
import scanner and instantiate scanner class;
declare your method with two parameters
declare a third variable;
set condition;
swap the parameter values if condition is met;
set second conditon based on result of first condition;
divide and assign remainder to the third variable;
swap the result;
in the main method, allow for user input;
Call the method;

*/
public class gcf {
    public static void main (String[]args){//start of main method
        Scanner input = new Scanner (System.in);//allow for user input
        System.out.println("Please enter the first integer: ");//prompt
        int a = input.nextInt();//initial user input
        System.out.println("Please enter a second interger: ");//prompt
        int b = input.nextInt();//second user input


       Divide(a,b);//call method
    }
   public static void Divide(int a, int b) {//start of your method

    int temp;
    // making 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 b
        a =b;
        b =temp;

    }
    System.out.println(a);//print to console
  }
}

Answer 16

import java.util.*;

public class BCD {

    public static void main(String[] args) {
        int k=1;
        Scanner in = new Scanner(System.in);
        int x = in.nextInt();
        int y = in.nextInt();
        for(int i=1;i<=Math.min(x,y);i++){
            if(x%i==0 && y%i==0)
                k=i;
        }
        System.out.println("the biggest common divisor is " + k);
    }
}

Answer 17

import java.util.*;
public class Greatest_common_Divisor
{

    public static void main (String[]args){
            Scanner input = new Scanner(System.in);
    System.out.println("Enter two integers: ");
    int n1 = input.nextInt();
    int n2 = input.nextInt();

    int d = 0;
    int e=0;
    int temp = 0;
    //finds the lowest value
    if(n1 < n2) {
        temp = n1;
        n1 = n2;
        n2 = temp;
    }

    for(d = n2;(n2%d!=0 || n1%d!= 0);d--){


    }

    System.out.println("The Greatest Common Divisor of " + n1 + " and " + n2 + " is " + d);

    }

}

Answer 18

int n1 = 12; // you can make the user insert n1,n2 using Scanner or JOptionPane
int n2 = 26;
int gcd = 1;
int k = 1;

while ((k <= n1) && (k <= n2)) {
    if ((n1 % k == 0) && (n2 % k == 0)) {
        gcd = k;
    }
    k++;
}

System.out.print("The Greatest Common divisor of The Two numbers IS :   " + gcd);

Answer 19

public int gcd(int num1, int num2) { 
    int max = Math.abs(num1);
    int min = Math.abs(num2);

    while (max > 0) {
        if (max < min) {
            int x = max;
            max = min;
            min = x;
        }
        max %= min;
    }

    return min;
}

Este método usa el algoritmo de Euclides para obtener el "Divisor común más grande" de dos enteros. Recibe dos enteros y devuelve el gcd de ellos. ¡así de fácil!