Comment trouver GCD, LCM sur un ensemble de chiffres
Quel serait le moyen le plus simple de calculer le plus grand diviseur commun et le plus petit Multiple commun sur un ensemble de nombres? Quelles fonctions mathématiques peuvent être utilisées pour trouver cette information?
13 réponses
J'ai utilisé l'algorithme D'Euclide pour trouver le plus grand diviseur commun de deux nombres; il peut être itéré pour obtenir le GCD d'un plus grand ensemble 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 multiple le moins commun est un peu plus délicat, mais la meilleure approche est probablement la réduction par le GCD , qui peut être itérée de la même manière:
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 n'y a pas de fonction de construction pour cela. Vous pouvez trouver le GCD de deux nombres en utilisant l'algorithme D'Euclide .
Pour un ensemble de nombre
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 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 souhaitez réellement), vous pouvez utiliser des expressions lambda pour résoudre fonctionnellement ceci:
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 pgcd fonctionnellement
- utilisé la syntaxe varargs pour une API plus facile (je n'étais pas sûr si la surcharge fonctionnerait correctement, mais c'est le cas sur ma machine)
- a transformé le gcd du
numbers-Array en syntaxe fonctionnelle, plus compacte et plus facile à lire (at moins si vous êtes habitué à la programmation fonctionnelle)
Cette approche est probablement légèrement plus lente en raison d'appels de fonctions supplémentaires, mais cela n'aura probablement pas d'importance 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<s;x++)
{
t=y*x;
}
if(s==t)
break;
}
return(s);
}
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();
}
PGCD:
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 cad faire comme ci-dessous:
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());
Fondamentalement pour trouver gcd et lcm sur un ensemble de nombres, vous pouvez utiliser la formule ci-dessous,
LCM(a, b) X HCF(a, b) = a * b
Pendant ce temps, en java, vous pouvez utiliser l'algorithme d'Euclide 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'Euclide.
Importer java.util.Scanner; classe publique 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
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);
}
}
}
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);
}
}
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 est d'obtenir tous les nombres à partir de '2'. ensuite, si l'instruction vérifie si le nombre (i) divise lcm s'il le fait, il ignore ce non. et si ce n'est pas le cas, la prochaine boucle est de trouver un non. ce qui peut diviser le nombre(i) si cela se produit, nous n'avons pas besoin de ce non. nous ne voulons que son facteur supplémentaire. donc, ici, si le drapeau est vrai, cela signifie qu'il y avait déjà des facteurs de non. "je" dans la lcm. nous divisons donc ces facteurs et multiplions le facteur supplémentaire en lcm. Si l' nombre n'est pas divisible par l'un de ses précédents n'. puis, quand il suffit de multiplier à la lcm.