Java 如何在一组数字上找到 GCD、LCM
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/4201860/
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
How to find GCD, LCM on a set of numbers
提问by user339108
What would be the easiest way to calculate Greatest Common Divisor and Least Common Multiple on a set of numbers? What math functions can be used to find this information?
在一组数字上计算最大公约数和最小公倍数的最简单方法是什么？可以使用哪些数学函数来查找此信息？
采纳答案by Jeffrey Hantin
I've used Euclid's algorithmto find the greatest common divisor of two numbers; it can be iterated to obtain the GCD of a larger set of numbers.
我使用欧几里得算法来找到两个数的最大公约数；可以迭代它以获得更大的一组数字的 GCD。
private static long gcd(long a, long b)
{
while (b > 0)
{
long temp = b;
b = a % b; // % is remainder
a = temp;
}
return a;
}
private static long gcd(long[] input)
{
long result = input[0];
for(int i = 1; i < input.length; i++) result = gcd(result, input[i]);
return result;
}
Least common multiple is a little trickier, but probably the best approach is reduction by the GCD, which can be similarly iterated:
最小公倍数有点棘手，但最好的方法可能是通过 GCD 减少，它可以类似地迭代：
private static long lcm(long a, long b)
{
return a * (b / gcd(a, b));
}
private static long lcm(long[] input)
{
long result = input[0];
for(int i = 1; i < input.length; i++) result = lcm(result, input[i]);
return result;
}
回答by J-16 SDiZ
There are no build in function for it. You can find the GCD of two numbers using Euclid's algorithm.
它没有内置功能。您可以使用欧几里德算法找到两个数字的 GCD 。
For a set of number
对于一组数
GCD(a_1,a_2,a_3,...,a_n) = GCD( GCD(a_1, a_2), a_3, a_4,..., a_n )
Apply it recursively.
递归地应用它。
Same for LCM:
LCM 也一样：
LCM(a,b) = a * b / GCD(a,b)
LCM(a_1,a_2,a_3,...,a_n) = LCM( LCM(a_1, a_2), a_3, a_4,..., a_n )
回答by RyuuGan
There is an Euclid's algorithmfor GCD,
有一个用于 GCD的欧几里德算法，
public int GCF(int a, int b) {
if (b == 0) return a;
else return (GCF (b, a % b));
}
By the way, aand bshould be greater or equal 0, and LCM= |ab| / GCF(a, b)
顺便说一句，a并且b应该大于或等于0，并且LCM=|ab| / GCF(a, b)
回答by saif
int lcmcal(int i,int y)
{
int n,x,s=1,t=1;
for(n=1;;n++)
{
s=i*n;
for(x=1;t<s;x++)
{
t=y*x;
}
if(s==t)
break;
}
return(s);
}
回答by user3026735
int gcf(int a, int b)
{
while (a != b) // while the two numbers are not equal...
{
// ...subtract the smaller one from the larger one
if (a > b) a -= b; // if a is larger than b, subtract b from a
else b -= a; // if b is larger than a, subtract a from b
}
return a; // or return b, a will be equal to b either way
}
int lcm(int a, int b)
{
// the lcm is simply (a * b) divided by the gcf of the two
return (a * b) / gcf(a, b);
}
回答by Rajeev sen
import java.util.Scanner; public class Lcmhcf {
导入 java.util.Scanner; 公共类 Lcmhcf {
/**
* @param args the command line arguments
*/
public static void main(String[] args) {
// TODO code application logic here
Scanner scan = new Scanner(System.in);
int n1,n2,x,y,lcm,hcf;
System.out.println("Enter any 2 numbers....");
n1=scan.nextInt();
n2=scan.nextInt();
x=n1;
y=n2;
do{
if(n1>n2){
n1=n1-n2;
}
else{
n2=n2-n1;
}
} while(n1!=n2);
hcf=n1;
lcm=x*y/hcf;
System.out.println("HCF IS = "+hcf);
System.out.println("LCM IS = "+lcm);
}
}
//## Heading ##By Rajeev Lochan Sen
回答by AdHominem
With Java 8, there are more elegant and functional ways to solve this.
在 Java 8 中，有更优雅、更实用的方法来解决这个问题。
LCM:
液晶模组：
private static int lcm(int numberOne, int numberTwo) {
final int bigger = Math.max(numberOne, numberTwo);
final int smaller = Math.min(numberOne, numberTwo);
return IntStream.rangeClosed(1,smaller)
.filter(factor -> (factor * bigger) % smaller == 0)
.map(factor -> Math.abs(factor * bigger))
.findFirst()
.getAsInt();
}
GCD:
GCD：
private static int gcd(int numberOne, int numberTwo) {
return (numberTwo == 0) ? numberOne : gcd(numberTwo, numberOne % numberTwo);
}
Of course if one argument is 0, both methods will not work.
当然，如果一个参数为 0，则两种方法都不起作用。
回答by Qw3ry
If you can use Java 8 (and actually want to) you can use lambda expressions to solve this functionally:
如果您可以使用 Java 8（并且实际上想要），您可以使用 lambda 表达式从功能上解决这个问题：
private static int gcd(int x, int y) {
return (y == 0) ? x : gcd(y, x % y);
}
public static int gcd(int... numbers) {
return Arrays.stream(numbers).reduce(0, (x, y) -> gcd(x, y));
}
public static int lcm(int... numbers) {
return Arrays.stream(numbers).reduce(1, (x, y) -> x * (y / gcd(x, y)));
}
I oriented myself on Jeffrey Hantin's answer, but
我以Jeffrey Hantin 的回答为导向，但是
- calculated the gcd functionally
- used the varargs-Syntax for an easier API (I was not sure if the overload would work correctly, but it does on my machine)
- transformed the gcd of the
numbers-Array into functional syntax, which is more compact and IMO easier to read (at least if you are used to functional programming)
- 以函数方式计算 gcd
- 使用 varargs-Syntax 来获得更简单的 API（我不确定重载是否能正常工作，但在我的机器上确实如此）
- 将
numbers-Array的 gcd转换为函数式语法，它更紧凑且 IMO 更易于阅读（至少如果您习惯了函数式编程）
This approach is probably slightly slower due to additional function calls, but that probably won't matter at all for the most use cases.
由于额外的函数调用，这种方法可能会稍微慢一些，但对于大多数用例来说，这可能根本无关紧要。
回答by NigerianJosh
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner input = new Scanner(System.in);
int n0 = input.nextInt(); // number of intended input.
int [] MyList = new int [n0];
for (int i = 0; i < n0; i++)
MyList[i] = input.nextInt();
//input values stored in an array
int i = 0;
int count = 0;
int gcd = 1; // Initial gcd is 1
int k = 2; // Possible gcd
while (k <= MyList[i] && k <= MyList[i]) {
if (MyList[i] % k == 0 && MyList[i] % k == 0)
gcd = k; // Update gcd
k++;
count++; //checking array for gcd
}
// int i = 0;
MyList [i] = gcd;
for (int e: MyList) {
System.out.println(e);
}
}
}
回答by parsa
for gcdyou cad do as below:
为gcd您 cad 做如下：
String[] ss = new Scanner(System.in).nextLine().split("\s+");
BigInteger bi,bi2 = null;
bi2 = new BigInteger(ss[1]);
for(int i = 0 ; i<ss.length-1 ; i+=2 )
{
bi = new BigInteger(ss[i]);
bi2 = bi.gcd(bi2);
}
System.out.println(bi2.toString());
