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

Question

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

Answer 1

he usado Algoritmo de Euclid encontrar el mayor divisor común de dos números; Se puede iterar para obtener el GCD de un conjunto más grande de números.

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últiplo menos común es un poco más complicado, pero probablemente el mejor enfoque es Reducción del GCD, que puede ser iterado de manera similar:

private static long lcm(long a, long b)
{
    return a * (b / gcd(a, b));
}

private static long gcd(long[] input)
{
    long result = input[0];
    for(int i = 1; i < input.length; i++) result = lcm(result, input[i]);
    return result;
}

Answer 2

Hay un Algoritmo de Euclid para GCD,

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

De paso, a y b debe ser mayor o igual 0, y LCM = |ab| / GCF(a, b)

Answer 3

No hay función de construcción para ello. Puede encontrar el GCD de dos números usando Algoritmo de Euclid.

Para un conjunto de número

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 )

Answer 4

Si puede usar Java 8 (y realmente desea), puede usar expresiones Lambda para resolver esto funcional:

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é Respuesta de Jeffrey Hantin, pero

• calculó el GCD funcionalmente
• Usé el varargs-syntax para una API más fácil (no estaba seguro de si la sobrecarga funcionaría correctamente, pero lo hace en mi máquina)
• transformó el GCD del numbers-Alabá en la sintaxis funcional, que es más compacta e IMO más fácil de leer (al menos si está acostumbrado a la programación funcional)

Este enfoque probablemente sea un poco más lento debido a llamadas de función adicionales, pero eso probablemente no importará en absoluto para la mayor cantidad de casos de uso.

Answer 5

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 6

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 7

Con Java 8, hay formas más elegantes y funcionales de 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.

Answer 8

por gcd USTED CAD HACE A BOTED:

    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 9

Básicamente para encontrar GCD y LCM en un conjunto de números que puede usar a continuación, Fórmula,

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

Mientras tanto en Java puedes usar el algoritmo de Euclid 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));
    }
}

Puedes referirte este Recurso para encontrar ejemplos sobre el algoritmo de Euclid.

Answer 10

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

Answer 11

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 12

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 13

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

Aquí, primero para Loop es para obtener todos los números a partir de '2'. Luego, si la declaración verifique si el número (i) divide LCM si lo hace, saltea que no. Y si no es así, lo siguiente para el bucle es para encontrar un no. que puede dividir el número (i) Si esto sucede, no necesitamos que no. Solo queremos su factor adicional. Así que aquí si la bandera es verdadera, esto significa que ya tenía algunos factores de no. 'I' en LCM. Entonces dividimos esos factores y multiplicamos el factor adicional a LCM. Si el número no es divisible por ninguno de sus no. luego cuando simplemente multiplíquelo al LCM.