Java : obtenir le plus grand diviseur commun

Question

J'ai vu qu'une telle fonction existe pour BigInteger es decir BigInteger#gcd . Existe-t-il d'autres fonctions en Java qui fonctionnent également pour d'autres types ( int , long o Integer ) ? Il semble que cela ait un sens car java.lang.Math.gcd (avec toutes sortes de surcharges) mais il n'est pas là. Est-il ailleurs ?

---

(Ne confondez pas cette question avec "comment mettre cela en œuvre moi-même", s'il vous plaît).

Answer 1

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

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

Vous pouvez aussi le faire en une ligne si vous aimez ce genre de choses :

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

Il faut noter qu'il y a absolument pas de Il n'y a pas de différence entre les deux car ils se compilent dans le même code d'octet.

Answer 2

Pour int et long, en tant que primitives, pas vraiment. Pour Integer, il est possible que quelqu'un en ait écrit un.

Étant donné que BigInteger est un sur-ensemble (mathématique/fonctionnel) de int, Integer, long et Long, si vous devez utiliser ces types, convertissez-les en BigInteger, faites le GCD et reconvertissez 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 3

Ou l'algorithme euclidien pour calculer le PGCD...

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

C'est exactement ce que propose Jakarta Commons Math.

ArithmeticUtils.gcd(int p, int q)

Answer 5

Le % va nous donner le pgcd entre deux nombres, cela signifie:- % ou mod de grand_nombre/petit_nombre sont =gcd, et on l'écrit en java comme ceci 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 : pour 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;
}