[알고리즘] #1 최대 공약수 구하기

최대 공약수 구하는 알고리즘

 

1. 두 수를 입력 받는다.

2. 큰 수를 작은 수로 나눈 나머지를 구한다.

3. 큰 수를 작은 수로 바꾸고

    작은 수에는 구한 나머지 수를 넣는다.

4. 작은 수가 0이 될 때까지 2-3번을 반복한다

5. max_num  min_num(=0)

    마지막 큰 수가 최대공약수이다.

 

< C/C++ >

#include <iostream>
using namespace std;

int main(){
    int n1, n2, max_num, min_num, mod;
    cin >> n1 >> n2;
    
    max_num = n1>n2?n1:n2;
    min_num = n1<n2?n1:n2;
    
    mod=1;
    while(min_num==0){
        mod=max_num % min_num;
        max_num=min_num;
        min_num=mod;
    }
    
    cout<< n1 <<"과 "<<n2<<"의 최대공약수: "<< mod;
    return 0;
}

 

< Python >

n1 = int(input())
n2= int(input())

if n1>n2:
	max_num=n1
    min_num=n2
else:
    max_num=n2
    min_num=n1
    
mod=1
while min_num!=0:
    mod = max_num % min_num
    max_num=min_num
    min_num=mod;
    
print("최대공약수: ", max_num);

< Java >

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        int n1, n2, maxN,minN, mod;
        Scanner in = new Scanner(System.in);
        System.out.print("Enter a number1: ");
        n1= in.nextInt();
        System.out.print("Enter a number2: ");
        n2=in.nextInt();
        maxN = n1>n2?n1:n2;
        minN = n1<n2?n1:n2;
        
        while(minN!=0){
            mod = maxN % minN;
            maxN = minN;
            minN = mod;
        }
        System.out.println("최대공약수: "+maxN);
    }
}