Java: Erhalten Sie den größten gemeinsamen Teiler

Habe ich gesehen, dass eine solche Funktion existiert für BigIntegerd.h. BigInteger#gcd. Gibt es andere Funktionen in Java, welche die arbeiten auch für andere Arten (intlong oder Integer)? Es scheint, dass das Sinn machen würde als java.lang.Math.gcd (mit allen Arten von überlastungen), aber es ist nicht da. Ist es irgendwo anders?

(Verwechseln Sie diese Frage mit "wie implementiere ich das selbst", bitte!)

InformationsquelleAutor der Frage Albert | 2010-10-24

greatest-common-divisor java

Für int und long, die als primitive, nicht wirklich. Für Integer, ist es möglich, jemand schrieb.

Gegeben, BigInteger ist eine (mathematische/funktionale) Obermenge von int, Integer, long, und Lange, wenn Sie brauchen, um diese Typen verwenden, konvertieren Sie in ein BigInteger, tun den GCD, und konvertieren das Ergebnis zurück.

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

Der bessere Weg:

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

InformationsquelleAutor der Antwort Tony Ennis

117

Soweit ich weiß, gibt es keine integrierte Methode für primitive. Aber etwas so einfaches wie das sollte den trick tun:
```
public int GCD(int a, int b) {
   if (b==0) return a;
   return GCD(b,a%b);
}
```
Können Sie auch eine Zeile, wenn man in diese Art der Sache:
```
public int GCD(int a, int b) { return b==0 ? a : GCD(b, a%b); }
```
Es sollte angemerkt werden, dass es absolut keine Unterschied zwischen den beiden, wie Sie kompilieren, um die gleiche byte-code.

InformationsquelleAutor der Antwort Matt

Oder der euklidische Algorithmus zur Berechnung der 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;
}

InformationsquelleAutor der Antwort Xorlev

11

Jakarta-Commons-Math hat genau das.

ArithmeticUtils.gcd(int p, int q)

InformationsquelleAutor der Antwort Tom Tucker
10

Verwenden Guave LongMath.gcd() und IntMath.gcd()

InformationsquelleAutor der Antwort Morad

Können Sie diese Implementierung der Binären GCD-Algorithmus

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

}

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

InformationsquelleAutor der Antwort linuxjava

6

Einige Implementierungen, die hier nicht ordnungsgemäß funktioniert, wenn beide zahlen negativ sind. gcd(-12, -18) ist 6, nicht -6.

Also absoluter Wert zurückgegeben werden soll, so etwas wie
```
public static int gcd(int a, int b) {
    if (b == 0) {
        return Math.abs(a);
    }
    return gcd(b, a % b);
}
```
InformationsquelleAutor der Antwort Robot Monk
5

Es sei denn, ich habe Guave, definiere ich so:
```
int gcd(int a, int b) {
  return a == 0 ? b : gcd(b % a, a);
}
```
InformationsquelleAutor der Antwort Alexey

Wenn Sie Java 1.5 oder höher, dann ist dies ein iterativer binären GCD-Algorithmus, die verwendet Integer.numberOfTrailingZeros() zur Verringerung der Zahl der Prüfungen und der Iterationen benötigt.

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

Unit-test:

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

InformationsquelleAutor der Antwort MT0

können wir verwenden rekursive Funktion zum finden 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));
    }
}

InformationsquelleAutor der Antwort Esann

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

InformationsquelleAutor der Antwort Gitau Harrison

Ich habe folgende Methode.

/**
 * @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);
}

InformationsquelleAutor der Antwort Isuru

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

InformationsquelleAutor der Antwort george ghawali

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

    }

}

InformationsquelleAutor der Antwort Oliver Queen

Benutzte ich diese Methode, die ich erstellt, als ich 14 Jahre alt war.

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

InformationsquelleAutor der Antwort John Doe

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

Diese Methode verwendet die Euklid ' s Algorithmus, um die "Größten Gemeinsamen Teiler" zweier zahlen. Es erhält zwei Ganzzahlen und gibt den gcd von Ihnen. so einfach!

InformationsquelleAutor der Antwort Mohsen

0

Ist es irgendwo anders?

Apache! - es hat sowohl gcd und lcm, so cool!

Jedoch aufgrund der Tiefe Ihrer Umsetzung, es ist langsamer im Vergleich zu einfachen handgeschriebenen version (falls es darauf ankommt).

InformationsquelleAutor der Antwort Boleslovas Švitrigaila

import java.io.*;
import java.util.*;
public class CandidateCode {
    public static void main(String args[] ) throws Exception {

    Scanner sc = new Scanner(System.in);
    int  m = sc.nextInt();
    int n  = sc. nextInt();
    int g = 1;
     for (int i = 1 ; i <= m && i <= n ; i++)
     {
         if((m%i==0)&&(n%i==0))
         g= i;
     }
     System.out.println(g);

   }
}

InformationsquelleAutor der Antwort malik arman

-3

% Uns geben wird, die gcd Zwischen zwei zahlen bedeutet das:-
% oder mod von big_number/small_number sind =gcd,
und wir schreiben es auf java wie diese big_number % small_number.

EX1: für zwei ganze zahlen

  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: für drei Ganzzahlen, die

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

InformationsquelleAutor der Antwort Mr-Al7lawe

-12

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

InformationsquelleAutor der Antwort user2003749

Schreibe einen Kommentar

Du musst angemeldet sein, um einen Kommentar abzugeben.