최소공배수, 최대공약수

// 최소 공배수 계산 메서드
  // 최소공배수는 엄청나게 큰 숫자가 나올 수도 있기에
  // long형으로 다루어야 합니다.
  public static long lcm(long a, long b) {
    int gcd_value = gcd((int)a, (int)b);

    if (gcd_value == 0) return 0; // 인수가 둘다 0일 때의 에러 처리

    return Math.abs( (a * b) / gcd_value );
  }


  // 최대 공약수 계산 함수; 최소 공배수 계산에 필요함
  // 최대 공약수는 그리 큰 숫자가 나오지 않기에 int형으로
  public static int gcd(int a, int b) {
    while (b != 0) {
      int temp = a % b;
      a = b;
      b = temp;
    }
    return Math.abs(a);
  }

=============================================================================

재귀함수로 최대공약수 구하기

public static int getGcd(int x, int y)

    {

        if(x % y == 0) return y;

        return getGcd(y, x%y);

   }

최소공배수 = x*y/getGcd(x,y);
==========================================
N개의 최대공약수, 최소공배수 구하기

/**************************************************************

    Problem: 1002

    User: a132034

    Language: Java

    Result: Success

    Time:158 ms

    Memory:9308 kb

****************************************************************/

 

 

import java.util.Arrays;

import java.util.Scanner;

 

public class Main{

    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);

        int N = sc.nextInt();

        int[] arr = new int[N];

         

        int GCD = 0, LCM = 0 ;

        for(int i = 0 ; i < N; ++i)

            arr[i] = sc.nextInt();

        Arrays.sort(arr);

        GCD = arr[N-1];

        LCM = arr[N-1];

 

        for(int i = N-2 ; i >= 0; --i)

        {

            int x, y;

            if(GCD > arr[i]){

                x = GCD; y = arr[i];

            }

            else{

                y = GCD; x = arr[i];

            }

            GCD = getGcd(x, y);

             

            if(LCM > arr[i]){

                x = LCM; y = arr[i];

            }

            else{

                y = LCM; x = arr[i];

            }

 

            LCM = (x * y) /  getGcd(x, y);

 

        }

        System.out.println(GCD + " " + LCM);        

    }

     

    public static int getGcd(int x, int y)

    {

        if(x % y == 0) return y;

        return getGcd(y, x%y);

    }

}

출처: http://dyndy.tistory.com/99 [DY N DY]