Comment trouver GCD, LCM sur un ensemble de nombres

Quelle serait la manière la plus simple de calculer le plus grand commun diviseur et le plus petit multiple commun sur un ensemble de nombres? Quelles fonctions mathématiques peuvent être utilisées pour trouver cette information?

J’ai utilisé l’algorithme d’ Euclide pour trouver le plus grand commun diviseur de deux nombres; il peut être itéré pour obtenir le GCD d’un plus grand nombre de nombres.

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

Le plus petit multiple commun est un peu plus compliqué, mais la meilleure approche est probablement la réduction par le GCD , qui peut être réitérée de la même façon:

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

Il y a un algorithme d’ Euclide pour GCD,

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

Par ailleurs, a et b devraient être supérieurs ou égaux à 0 , et LCM = |ab| / GCF(a, b) |ab| / GCF(a, b)

Il n’y a pas de fonction intégrée pour cela. Vous pouvez trouver le GCD de deux nombres en utilisant l’algorithme d’Euclid .

Pour un ensemble de nombres

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

Appliquez-le récursivement.

Même chose pour 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 vous pouvez utiliser Java 8 (et que vous le voulez réellement), vous pouvez utiliser des expressions lambda pour résoudre ce problème fonctionnellement:

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

Je me suis orienté sur la réponse de Jeffrey Hantin , mais

  • calculé le gcd fonctionnellement
  • utilisé la syntaxe varargs pour une API plus facile (je n’étais pas sûr que la surcharge fonctionnerait correctement, mais c’est le cas sur ma machine)
  • a transformé le gcd des numbers -Array en syntaxe fonctionnelle, qui est plus compacte et IMO plus facile à lire (du moins si vous êtes habitué à la functional programming)

Cette approche est probablement légèrement plus lente en raison des appels de fonctions supplémentaires, mais cela ne changera probablement pas du tout pour la plupart des cas d’utilisation.

 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 lcmcal(int i,int y) { int n,x,s=1,t=1; for(n=1;;n++) { s=i*n; for(x=1;t 

Avec Java 8, il existe des moyens plus élégants et fonctionnels pour résoudre ce problème.

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

Bien sûr, si un argument est 0, les deux méthodes ne fonctionneront pas.

pour gcd vous faites comme ci-dessous:

  Ssortingng[] ss = new Scanner(System.in).nextLine().split("\\s+"); BigInteger bi,bi2 = null; bi2 = new BigInteger(ss[1]); for(int i = 0 ; i 

Fondamentalement, pour trouver gcd et lcm sur un ensemble de chiffres que vous pouvez utiliser sous la formule,

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

Pendant ce temps en Java, vous pouvez utiliser l’algorithme d’euclid pour trouver gcd et lcm, comme ceci

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

Vous pouvez vous référer à cette ressource pour trouver des exemples sur l’algorithme d’euclid.

import java.util.Scanner; classe publique Lcmhcf {

 /** * @param args the command line arguments */ public static void main(Ssortingng[] 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 
 import java.util.Scanner; public class Main { public static void main(Ssortingng[] 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); } } } 
 import java.util.*; public class lcm { public static void main(Ssortingng 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); } } 
 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; } 

ici, la première pour la boucle consiste à obtenir tous les nombres à partir de «2». alors si l’instruction vérifie si le nombre (i) divise lcm si c’est le cas, alors il saute que non. et si ce n’est pas le cas, la prochaine étape consiste à trouver un non. qui peut diviser le nombre (i) si cela se produit, nous n’avons pas besoin de cela non. nous voulons seulement son facteur supplémentaire. Donc, si le drapeau est vrai, cela signifie qu’il y avait déjà des facteurs de non. ‘i’ en lcm. nous divisons donc ces facteurs et multiplions le facteur supplémentaire en lcm. Si le nombre n’est divisible par aucun de ses précédents no. puis quand il suffit de le multiplier au lcm.