숫자 집합에서 GCD, LCM을 찾는 방법

숫자 집합에서 GCD, LCM을 찾는 방법

---

숫자 집합에서 최대 공약수와 최소 공배수를 계산하는 가장 쉬운 방법은 무엇입니까? 이 정보를 찾기 위해 어떤 수학 함수를 사용할 수 있습니까?

---

저는 두 수의 최대 공약수를 찾기 위해 Euclid의 알고리즘 을 사용했습니다 . 더 큰 숫자 세트의 GCD를 얻기 위해 반복 할 수 있습니다.

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

최소 공배수는 약간 까다 롭지 만 아마도 가장 좋은 방법은 GCD에 의한 감소이며 유사하게 반복 될 수 있습니다.

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

---

가 유클리드의 알고리즘은 , GCD에 대한

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

그런데, a및 b크거나 같아야 0하고, LCM =|ab| / GCF(a, b)

---

그것에 대한 내장 기능이 없습니다. Euclid의 알고리즘을 사용하여 두 숫자의 GCD를 찾을 수 있습니다 .

숫자 세트

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

재귀 적으로 적용하십시오.

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 )

---

Java 8을 사용할 수 있고 실제로 원하는 경우 람다 표현식을 사용하여이 문제를 기능적으로 해결할 수 있습니다.

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

나는 Jeffrey Hantin의 대답을 지향 했지만

• 기능적으로 gcd 계산
• 더 쉬운 API를 위해 varargs-Syntax를 사용했습니다 (오버로드가 제대로 작동하는지 확실하지 않았지만 내 컴퓨터에서 작동합니다)
• numbers-Array 의 gcd 를 기능적 구문으로 변환하여 더 간결하고 IMO를 더 쉽게 읽을 수 있습니다 (최소한 함수형 프로그래밍에 익숙한 경우).

이 접근 방식은 추가 함수 호출로 인해 약간 느릴 수 있지만 대부분의 사용 사례에서는 전혀 문제가되지 않습니다.

---

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

---

Java 8에는이 문제를 해결할 수있는보다 우아하고 기능적인 방법이 있습니다.

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

물론 하나의 인수가 0이면 두 방법 모두 작동하지 않습니다.

---

gcd당신을 위해 cad는 아래와 같이합니다 :

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

---

기본적으로 숫자 집합에서 gcd 및 lcm을 찾으려면 아래 공식을 사용할 수 있습니다.

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

한편 자바에서는 유클리드의 알고리즘을 사용하여 다음과 같이 gcd 및 lcm을 찾을 수 있습니다.

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

이 리소스를 참조 하여 유클리드의 알고리즘에 대한 예제를 찾을 수 있습니다 .

---

import java.util.Scanner; 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;
        }

here, first for loop is for getting every numbers starting from '2'. then if statement check whether the number(i) divides lcm if it does then it skip that no. and if it doesn't then next for loop is for finding a no. which can divides the number(i) if this happens we don't need that no. we only wants its extra factor. so here if the flag is true this means there already had some factors of no. 'i' in lcm. so we divide that factors and multiply the extra factor to lcm. If the number isn't divisible by any of its previous no. then when simply multiply it to the lcm.

참고URL : https://stackoverflow.com/questions/4201860/how-to-find-gcd-lcm-on-a-set-of-numbers