알고리즘 기초 - 6 (최대 공약수 구하기)

최대 공약수란 ?

 

2개 이상의 수의 공통된 약수 중에 가장 큰 수 이다.

 

EX ) 10의 약수 : 1, 2, 5, 10

  15의 약수 : 1, 3, 5, 15

 

10과 15의 공약수 : 1, 5

 

10과 15의 최대 공약수 = 5

 

 

 

Main.java

 

import java.io.IOException;
import java.util.Scanner;
 
public class Main {
 
    public static void main(String[] str) throws IOException {
 
    int a = 12;
    
    int b = 18;
    
    //  두 수 중에 어느수가 클지 알 수 없으므로 small과 big 변수를 만들어 
    //  큰 수와 작은 수를 따로 저장해준다.
    
    int small;
    int big;
    
    if(a > b){
        
        big = a;
        small = b;
        
    }else if (b > a) {
        
        big = b;
        small = a;
        
    }
    
    //gcd는 두수를 각각 나누어서 0이 나오는 수 (공약수)
    
    int gcd = 1;
    
    for (int i = 1; i <= small; i++){
        
        if (big % i == 0 && small % i == 0){
            
            gcd = i;
           
            }
    System.out.println("두수의 최대 공약수는 ?"+i);
        }
    }
}
 
 

 

 

 

 

출처

 

https://www.youtube.com/watch?v=jdnGckTvZ64&list=PLVoihNyHW4xkm_KJ8_N8X7F6EQP4uSRyR&index=7