유클리드 호제법 (최대공약수와 최소공배수)

최대공약수와 최소공배수를 구하는 알고리즘이다

 

 

방법은 아래와 같다 (출처)

1. 입력으로 두 수 m,n(m>n)이 들어온다.
2. n이 0이라면, m을 출력하고 알고리즘을 종료한다.
3. m이 n으로 나누어 떨어지면, n을 출력하고 알고리즘을 종료한다.
4. 그렇지 않으면, m을 n으로 나눈 나머지를 새롭게 m에 대입하고, m과 n을 바꾸고 3번으로 돌아온다.

이렇게 최대공약수를 구한다

1 2 3 4 5

public static int gcd(int p, int q) {     if (q == 0) return p;     return gcd(q, p%q);  } Colored by Color Scripter

cs

 

이를 자바 코드로 풀면 위와 같다(첨부한 링크에 그대로 있는 코드)

 

위의 코드가 최대공약수를 구하는 알고리즘이고,

최소공배수는 두 수를 곱한 뒤 최대공약수로 나누면 된다 즉, p * q / gcd