How to find GCD, LCM on a set of numbers
JavaMathGreatest Common-DivisorLcmJava Problem Overview
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?
Java Solutions
Solution 1 - Java
I've used http://en.wikipedia.org/wiki/Euclid%27s_algorithm">Euclid's algorithm to find the greatest common divisor of two numbers; it can be iterated to obtain the GCD of a larger set of numbers.
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 http://en.wikipedia.org/wiki/Least_common_multiple#Reduction_by_the_greatest_common_divisor">reduction by the GCD, which can be similarly iterated:
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;
}
Solution 2 - Java
There is an Euclid's algorithm for GCD,
public int GCF(int a, int b) {
if (b == 0) return a;
else return (GCF (b, a % b));
}
By the way, a and b should be greater or equal 0, and LCM = |ab| / GCF(a, b)
Solution 3 - Java
There are no build in function for it. You can find the GCD of two numbers using Euclid's algorithm.
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(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 )
Solution 4 - Java
If you can use Java 8 (and actually want to) you can use lambda expressions to solve this functionally:
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
- 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)
This approach is probably slightly slower due to additional function calls, but that probably won't matter at all for the most use cases.
Solution 5 - Java
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);
}
Solution 6 - Java
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);
}
Solution 7 - Java
With Java 8, there are more elegant and functional ways to solve this.
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:
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.
Solution 8 - Java
for gcd you cad do as below:
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());
Solution 9 - Java
public class HcfLcm {
public static void main(String[] args) {
System.out.println("HCF: "+ getHcf(20, 15)); //5
System.out.println("LCM: "+ getLcm2(20, 15)); //60
}
private static Integer getLcm2(int n1, int n2) {
int lcm = Math.max(n1, n2);
// Always true
while (true) {
if (lcm % n1 == 0 && lcm % n2 == 0) {
break;
}
++lcm;
}
return lcm;
}
private static Integer getLcm(int i, int j) {
int hcf = getHcf(i, j);
return hcf * i/hcf * j/hcf; // i*j*hcf
}
private static Integer getHcf(int i, int j) {
while(i%j != 0) {
int temp = i%j;
i = j;
j = temp;
}
return j;
}
}
Solution 10 - Java
import java.util.Scanner; public class 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
Solution 11 - Java
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);
}
}
}
Solution 12 - Java
import java.util.*;
public class lcm {
public static void main(String args[])
{
int lcmresult=1;
System.out.println("Enter the number1: ");
Scanner s=new Scanner(System.in);
int a=s.nextInt();
System.out.println("Enter the number2: ");
int b=s.nextInt();
int max=a>b?a:b;
for(int i=2;i<=max;i++)
{
while(a%i==0||b%i==0)
{
lcmresult=lcmresult*i;
if(a%i==0)
a=a/i;
if(b%i==0)
b=b/i;
if(a==1&&b==1)
break;
}
}
System.out.println("lcm: "+lcmresult);
}
}
Solution 13 - Java
int lcm = 1;
int y = 0;
boolean flag = false;
for(int i=2;i<=n;i++){
if(lcm%i!=0){
for(int j=i-1;j>1;j--){
if(i%j==0){
flag =true;
y = j;
break;
}
}
if(flag){
lcm = lcm*i/y;
}
else{
lcm = lcm*i;
}
}
flag = false;
}
here, first for loop is for getting every numbers starting from '2'. then if statement check whether the number(i) divides lcm if it does then it skip that no. and if it doesn't then next for loop is for finding a no. which can divides the number(i) if this happens we don't need that no. we only wants its extra factor. so here if the flag is true this means there already had some factors of no. 'i' in lcm. so we divide that factors and multiply the extra factor to lcm. If the number isn't divisible by any of its previous no. then when simply multiply it to the lcm.