Java: получить наибольший общий делитель

Question

Я видел, что такая функция существует для BigInteger, то есть BigInteger#gcd. Существуют ли другие функции на Java, которые также работают для других типов (int, long или Integer)? Кажется, это имеет смысл как java.lang.Math.gcd (со всеми видами перегрузок), но его там нет. Это где-то еще?

---

(Не путайте этот вопрос «как мне это реализовать себя», пожалуйста!)

Answer 1

Для междунар и долго, как примитивы, а не на самом деле. Для Integer, возможно, кто-то написал один.

Учитывая, что BigInteger является (математическим/функциональным) супермножеством int, Integer, long и Long, если вам нужно использовать эти типы, конвертировать их в BigInteger, делать GCD и преобразовывать результат обратно.

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

Лучший способ:

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

Насколько я знаю, не существует какой-либо встроенный метод для примитивов. Но что-то же просто, как это следует сделать трюк:

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

Вы можете также одна линия, если вы в такого рода вещи:

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

Следует отметить, что абсолютно no Разница между ними при компиляции одного и того же байтового кода.

Answer 3

Или алгоритм Евклида для вычисления НОД ...

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

Jakarta Commons Math имеет именно это.

ArithmeticUtils.gcd(int p, int q)

Answer 5

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 6

% собирается дать нам НОД между двумя числами, это означает: - % или мод из big_number/small_number являются = НОД, и записать его на Java, как это big_number % small_number ,

EX1: два целых

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

ЕХ2: три целых

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 7

Вы можете использовать эту реализацию Binary GCD algorithm

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

}

F ром http://introcs.cs.princeton.edu/java/23recursion/BinaryGCD.java.html

Answer 8

Использование гуавы LongMath.gcd() и IntMath.gcd()

Answer 9

Некоторые реализации здесь не работают правильно, если оба числа отрицательны. gcd (-12, -18) равно 6, а не -6.

Так абсолютное значение должно быть возвращено, что-то вроде

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

Answer 10

Если вы используете Java 1.5 или более поздней версии, то это итеративный бинарный алгоритм НОД, который использует Integer.numberOfTrailingZeros(), чтобы уменьшить количество проверок и итераций.

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

испытания Единица измерения:

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

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

Если я не имею Guava, я определяю так:

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

Answer 13

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 14

Я использовал следующий метод.

/** 
* @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 15

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

    } 

}