Comment trouver GCD, LCM sur un ensemble de nombres

Question

Quelle serait la meilleure façon de calculer et grand commun diviseur commun multiple sur un ensemble de nombres? Quelles sont les fonctions mathématiques peuvent être utilisées pour trouver cette information?

Answer 1

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

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

commun multiple est un peu plus délicat, mais sans doute la meilleure approche est la réduction

Answer 2

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 doit être supérieure ou égale 0, et LCM = |ab| / GCF(a, b)

Il n'y a pas de construction en fonction pour elle. Vous pouvez trouver le PGCD de deux nombres en utilisant 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 )

Appliquer récursive.

Idem 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 voulez réellement), vous pouvez utiliser des expressions lambda pour résoudre ce plan fonctionnel:

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 Jeffrey Hantin , mais

• a calculé le GCD fonctionnel
• utilisé le varargs-syntaxe pour une API plus facile (je ne sais pas si la surcharge serait correctement, mais il le fait sur ma machine)
• transformé le GCD du numbers-Array dans la syntaxe fonctionnelle, qui est plus compact et plus facile à lire l'OMI (au moins si vous êtes habitué à la programmation fonctionnelle)

Cette approche est probablement un peu plus lent en raison d'appels de fonctions supplémentaires, mais qui ne comptera 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<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();
}

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 fonctionnent pas.

pour gcd vous càd faites 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 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 celui-ci

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

Vous pouvez consulter cette ressources pour trouver des exemples sur l'algorithme d'Euclide.

java.util.Scanner d'importation; 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

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, d'abord pour la boucle est pour obtenir tous les numéros à partir de « 2 ». alors si la déclaration vérifie si le nombre (i) divise LCM si elle ne puis ignorer que non. et si elle ne le fait pas alors la prochaine boucle est de trouver un non. qui peut diviser le nombre (i) si cela arrive, nous ne avons pas besoin que personne. nous ne veut que son facteur supplémentaire. alors ici si le drapeau est vrai, cela signifie qu'il avait déjà quelques facteurs de non. 'I' dans LCM. donc nous divisons que les facteurs et multiplier le facteur supplémentaire à LCM. Si le nombre est divisible par aucun de ses pas précédent. puis quand il suffit de multiplier le lcm.

Answer 3

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 doit être supérieure ou égale 0, et LCM = |ab| / GCF(a, b)

Answer 4

Il n'y a pas de construction en fonction pour elle. Vous pouvez trouver le PGCD de deux nombres en utilisant 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 )

Appliquer récursive.

Idem 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 )

Answer 5

Si vous pouvez utiliser Java 8 (et que vous voulez réellement), vous pouvez utiliser des expressions lambda pour résoudre ce plan fonctionnel:

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 Jeffrey Hantin , mais

• a calculé le GCD fonctionnel
• utilisé le varargs-syntaxe pour une API plus facile (je ne sais pas si la surcharge serait correctement, mais il le fait sur ma machine)
• transformé le GCD du numbers-Array dans la syntaxe fonctionnelle, qui est plus compact et plus facile à lire l'OMI (au moins si vous êtes habitué à la programmation fonctionnelle)

Cette approche est probablement un peu plus lent en raison d'appels de fonctions supplémentaires, mais qui ne comptera probablement pas du tout pour la plupart des cas d'utilisation.

Answer 6

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

Answer 7

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

Answer 8

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 fonctionnent pas.

Answer 9

pour gcd vous càd faites 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());

Answer 10

Fondamentalement 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 celui-ci

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

Vous pouvez consulter cette ressources pour trouver des exemples sur l'algorithme d'Euclide.

Answer 11

java.util.Scanner d'importation; 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

Answer 12

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

            }

            }

        }

Answer 13

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

Answer 14

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, d'abord pour la boucle est pour obtenir tous les numéros à partir de « 2 ». alors si la déclaration vérifie si le nombre (i) divise LCM si elle ne puis ignorer que non. et si elle ne le fait pas alors la prochaine boucle est de trouver un non. qui peut diviser le nombre (i) si cela arrive, nous ne avons pas besoin que personne. nous ne veut que son facteur supplémentaire. alors ici si le drapeau est vrai, cela signifie qu'il avait déjà quelques facteurs de non. 'I' dans LCM. donc nous divisons que les facteurs et multiplier le facteur supplémentaire à LCM. Si le nombre est divisible par aucun de ses pas précédent. puis quand il suffit de multiplier le lcm.