Java：获得最大公约数
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/4009198/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Java: get greatest common divisor
提问by Albert
I have seen that such a function exists for BigInteger, i.e. BigInteger#gcd. Are there other functions in Java which also work for other types (int, longor Integer)? It seems this would make sense as java.lang.Math.gcd(with all kinds of overloads) but it is not there. Is it somewhere else?
我已经看到这样的函数存在于BigInteger，即BigInteger#gcd。Java 中是否有其他函数也适用于其他类型（int,long或Integer）？这似乎是有道理的java.lang.Math.gcd（有各种重载），但它不存在。是别的地方吗？
(Don't confuse this question with "how do I implement this myself", please!)
（请不要将此问题与“我如何自己实现”混淆！）
采纳答案by Tony Ennis
For int and long, as primitives, not really. For Integer, it is possible someone wrote one.
对于 int 和 long，作为原语，不是真的。对于整数，可能有人写了一个。
Given that BigInteger is a (mathematical/functional) superset of int, Integer, long, and Long, if you need to use these types, convert them to a BigInteger, do the GCD, and convert the result back.
鉴于 BigInteger 是 int、Integer、long 和 Long 的（数学/函数）超集，如果您需要使用这些类型，请将它们转换为 BigInteger，执行 GCD，然后将结果转换回来。
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();
}
回答by Matt
As far as I know, there isn't any built-in method for primitives. But something as simple as this should do the trick:
据我所知，原语没有任何内置方法。但是像这样简单的事情应该可以解决问题：
public int gcd(int a, int b) {
if (b==0) return a;
return gcd(b,a%b);
}
You can also one-line it if you're into that sort of thing:
如果你喜欢这种事情，你也可以单行它：
public int gcd(int a, int b) { return b==0 ? a : gcd(b, a%b); }
It should be noted that there is absolutely nodifference between the two as they compile to the same byte code.
应该注意的是，两者之间绝对没有区别，因为它们编译为相同的字节码。
回答by Xorlev
Or the Euclidean algorithm for calculating the GCD...
或者计算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;
}
回答by Tom Tucker
回答by Mr-Al7lawe
The % going to give us the gcd Between two numbers, it means:-
% or mod of big_number/small_number are =gcd,
and we write it on java like this big_number % small_number.
% 将给我们两个数字之间的 gcd，这意味着：- big_number/small_number 的 % 或 mod 是 =gcd，我们像这样在 java 上写它 big_number % small_number。
EX1: for two integers
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;
}
EX2: for three integers
EX2：对于三个整数
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;
}
回答by linuxjava
You can use this implementation of Binary GCD algorithm
您可以使用此二进制 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));
}
}
}
From http://introcs.cs.princeton.edu/java/23recursion/BinaryGCD.java.html
来自http://introcs.cs.princeton.edu/java/23recursion/BinaryGCD.java.html
回答by Morad
Use Guava LongMath.gcd()and IntMath.gcd()
回答by Robot Monk
Some implementations here are not working correctly if both numbers are negative. gcd(-12, -18) is 6, not -6.
如果两个数字都是负数，则此处的某些实现将无法正常工作。gcd(-12, -18) 是 6，而不是 -6。
So an absolute value should be returned, something like
所以应该返回一个绝对值，比如
public static int gcd(int a, int b) {
if (b == 0) {
return Math.abs(a);
}
return gcd(b, a % b);
}
回答by MT0
If you are using Java 1.5 or later then this is an iterative binary GCD algorithm which uses Integer.numberOfTrailingZeros()to reduce the number of checks and iterations required.
如果您使用的是 Java 1.5 或更高版本，那么这是一种迭代二进制 GCD 算法，用于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;
}
}
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 );
}
}
}
回答by Gitau Harrison
/*
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
}
}
