최대공약수 최소공배수 구하기

최대공약수 최소공배수 구하기

최대공약수 접근방법

1. 최대공약수는 두개의 값을 받아 두개의 값 모두 같은 수로 나누어 나머지가 0이 되는 공통되는 수를 찾는 것을 말한다.

2. 두 수 value1, value2 (15, 35) 를 받고 2개의 수를 비교해 작은 수(15)를 변수(a)에 담고  

3. value1과 value2를 각각 변수(a)로 나누었을때 ( value1 % 변수a == 0 ) && ( value2 % 변수a == 0 ) 둘다 나머지가 0이 나오면 

4. 최대공약수이다. 둘다 나머지가 0 이 나오지 않으면 둘다 나머지가 0이 나올 때 까지 변수a값을 -1 씩 감소시키며 반복한다.

유클리드 접근방법

1. 재귀 형식으로 접근한다.

value1과 value2 값을 받아 앞의값 % 뒤에값이 0 이 나오지 않으면 반복한다.

나머지가 0이 나오면 최대공약수를 리턴한다.

myMethod2(value2, value1%value2)

최소공배수 접근방법

1.  value1 * value2 / 앞서 구한 최대공약수 = 최소공배수이다.

package test1;
 
import java.util.Scanner;
 
public class Gcd_Lcm {
 
    public static void main(String[] args) {
        // TODO Auto-generated method stub
 
        Scanner scan = new Scanner(System.in);
         
        System.out.println("숫자 2개 입력:");
 
        int value1, value2;
        value1 = scan.nextInt();
        value2 = scan.nextInt();
                
        pubMethod1 pub_method1 = new pubMethod1();
        
        // gcb
        pub_method1.myMethod1(value1, value2);
        System.out.println("gcb(최대공약수): "+pub_method1.myMethod1(value1, value2));
        
        // 유클리드
        pub_method1.myMethod2(value1, value2);
        System.out.println("유클리드: "+pub_method1.myMethod2(value1, value2));
        
        // lcm
        pub_method1.myMethod3(value1, value2);
        System.out.println("lcm(최소공배수): "+pub_method1.myMethod3(value1, value2));
    }
 
}
 
class pubMethod1{
    
    // 1. 일반적인 gcb(최대공약수) 구하기
    public int myMethod1(int value1, int value2){
        int minNum1 = Math.min(value1,value2);
        while(true){
            if(value1%minNum1==0 && value2%minNum1==0){
                return minNum1;
            }
            minNum1-=1;
        }
    }
    
    // 2. 유클리드 알고리즘
    // gcb(a,b) = gcb(b, a%b)
    public int myMethod2(int value1, int value2){ // 40 20
        if(value2==0){
            return value1;
        }else{
            return myMethod2(value2, value1%value2); // 20 , 40 / 20 
        }
    }
    
    // 3. lcm(최소공배수) 구하기
    public int myMethod3(int value1, int value2){
        return value1 * value2 / myMethod1(value1, value2);
    }
    
}

출력 결과

마지막으로 해당 소스를 첨부한다.

Gcd_Lcm.java