Java: obtenir le plus grand commun diviseur

Question

Je l'ai vu qu'une telle fonction existe pour BigInteger, ie BigInteger#gcd . Y at-il d'autres fonctions en Java qui fonctionnent aussi pour d'autres types (int, long ou Integer)? Il semble que ce serait logique que java.lang.Math.gcd (avec toutes sortes de surcharges), mais il n'y est pas. Est-il ailleurs?

---

(Ne pas confondre cette question avec « comment puis-je mettre moi-même », s'il vous plaît!)

Answer 1

Pour int et long, comme primitives, pas vraiment. Pour entier, il est possible que quelqu'un a écrit un.

Étant donné que BigInteger est un surensemble (mathématique / fonctionnelle) d'int, Entier long, et Long, si vous avez besoin d'utiliser ces types, les convertir en un BigInteger, faire le GCD, et reconvertir le résultat.

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 2

Pour autant que je sache, il n'y a pas de méthode intégrée pour les primitives. Mais quelque chose d'aussi simple que cela devrait faire l'affaire:

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

Vous pouvez également une ligne si vous êtes dans ce genre de chose:

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

Il convient de noter qu'il n'y a absolument pas différence entre les deux comme ils compilent le même code d'octets.

Answer 3

Ou l'algorithme d'Euclide pour le calcul du 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 4

Utilisez Goyave LongMath.gcd() et IntMath.gcd()

Answer 5

Jakarta Commons Math a exactement cela.

ArithmeticUtils.gcd (int p, q int)

Answer 6

À moins que je goyave, je définis comme ceci:

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

Answer 7

Vous pouvez utiliser cette implémentation de

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 8

Certaines mises en œuvre ici ne fonctionnent pas correctement si les deux chiffres sont négatifs. gcd (-12, -18) est 6, et non pas -6.

Ainsi, une valeur absolue doit être retourné, quelque chose comme

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

Answer 9

on peut utiliser la fonction récursive pour GCD find

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 10

Si vous utilisez Java 1.5 ou version ultérieure, alors c'est un algorithme de GCD binaire itérative qui utilise Integer.numberOfTrailingZeros() pour réduire le nombre de contrôles et itérations nécessaires.

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

Test unitaire:

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

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

Cette méthode utilise l'algorithme de Euclide pour obtenir le « PGCD » de deux entiers. Il reçoit deux entiers et retourne le GCD d'entre eux. tout aussi simple que cela!

Answer 12

/*
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 13

J'ai utilisé cette méthode que je crée quand j'avais 14 ans.

    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 14

  

Est-il ailleurs?

Apache - il a à la fois GCD et LCM, tellement cool

Cependant, en raison de leur mise en œuvre de profondeur, il est plus lent par rapport à la version simple, écrite à la main (si elle importe).

Answer 15

Les fonctions de GCD fournies par Commons-Math et Goyave ont quelques différences.

• Commons-Math jette un ArithematicException.class seulement pour Integer.MIN_VALUE ou Long.MIN_VALUE.
  • Dans le cas contraire, gère la valeur en tant que valeur absolue.
• Guava déclenche une IllegalArgumentException.class pour toutes les valeurs négatives.

Answer 16

Le% va nous donner le GCD entre deux nombres, cela signifie: - % Ou mod de big_number / small_number sont = gcd, et nous écrivons sur java comme ça big_number % small_number.

EX1: pour deux entiers

  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: trois entiers

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