multiple least geeksforgeeks gcd euclid common java math greatest-common-divisor lcm

java - least - lcm calculator



Cómo encontrar GCD, LCM en un conjunto de números (16)

// para encontrar lcm de dos números [forma realmente fácil]

clase lcm

{

static void main(int n1,int n2) { int lcm; int a=n1; int b=n2; System.out.println("/f"); if(n1==0||n2==0) { System.out.println("enter different number"); } else { while(a!=b) { if(a>b) { a=a-b; } else { b=b-a; } } int GCD=a; lcm=(n1*n2)/GCD; System.out.println("the LCM is "+lcm); }

}}

ese es un método realmente fácil ... [intente comprenderlo usted mismo porque la codificación de Cuz significa entender ... :)]

¿Cuál sería la forma más fácil de calcular el mayor divisor común y el mínimo común múltiplo en un conjunto de números? ¿Qué funciones matemáticas se pueden usar para encontrar esta información?


Básicamente para encontrar gcd y lcm en un conjunto de números, puede usar la fórmula siguiente,

LCM(a, b) X HCF(a, b) = a * b

Mientras tanto, en Java puedes usar el algoritmo de euclides para encontrar gcd y lcm, como este

public static int GCF(int a, int b) { if (b == 0) { return a; } else { return (GCF(b, a % b)); } }

Puede consultar this recurso para encontrar ejemplos en el algoritmo de euclid.


Con Java 8, hay formas más elegantes y funcionales para resolver esto.

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

Por supuesto, si un argumento es 0, ambos métodos no funcionarán.


Hay un algoritmo de Euclides para GCD,

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

Por cierto, a y b deberían ser mayores o iguales a 0 , y LCM = |ab| / GCF(a, b) |ab| / GCF(a, b)


He usado el algoritmo de Euclides para encontrar el mayor divisor común de dos números; puede repetirse para obtener el GCD de un conjunto de números más grande.

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

El mínimo común múltiplo es un poco más complicado, pero probablemente el mejor enfoque es la reducción por GCD , que se puede repetir de manera similar:

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



No hay construcción en función para eso. Puedes encontrar el GCD de dos números usando el algoritmo de Euclides .

Para un conjunto de números

GCD(a_1,a_2,a_3,...,a_n) = GCD( GCD(a_1, a_2), a_3, a_4,..., a_n )

Aplicarlo recursivamente.

Lo mismo para 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 )


Si puede usar Java 8 (y realmente quiere) puede usar expresiones lambda para resolver esto funcionalmente:

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

Me orienté sobre la respuesta de Jeffrey Hantin , pero

  • calculado el GCD funcionalmente
  • usé varargs-Syntax para una API más fácil (no estaba seguro de si la sobrecarga funcionaría correctamente, pero sí en mi máquina)
  • transformó el gcd de los numbers -Array en sintaxis funcional, que es más compacta y más fácil de leer en IMO (al menos si está acostumbrado a la programación funcional)

Este enfoque es probablemente un poco más lento debido a las llamadas a funciones adicionales, pero eso probablemente no importará para la mayoría de los casos de uso.


import java.util.Scanner; clase pública 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


para gcd usted cad hace lo siguiente:

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


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


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


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


int lcm(int x,int y){ int i=1; while(true){ if(!(x*i)%y) return x*i; i++; }


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


int main() { int n1,n2,num1,num2,rem,gcd,lcm; printf("Enter a number:"); scanf("%d %d",&num1,&num2); num1=n1; num2=n2; while(num2!=0) { rem=num1%num2; num1=num2; num2=rem; } gcd=num1; lcm=(n1*n2)/gcd; printf("Gcd=%d/n",gcd); printf("Lcm=%d/n",lcm); }