4장 수학 - (2) 최대공약수

1. 최대공약수(Greatest Common Divisor)

-최대공약수는 줄여서 GCD라고 쓴다.

-두 수 A와 B의 최대공약수 G는 A와 B의 공통된 약수 중에서 가장 큰 정수이다.

-최대공약수를 구하는 가장 쉬운 방법은 2부터 min(A,B)까지 모든 정수로 나우어 보는 방법

-최대공약수가 1인 두 수를 서로소(Coprime)이라고 한다.

(코드)

int g=1;

for(int i=2;i<=min(a,b);i++){

if(a%i == 0 && b%i == 0)

g=i;

}

=> 시간복잡도 O(N)

-위의 방법보다 빠른 방법이 있다. => 유클리드 호제법(Euclidean Algorithm)

2. 유클리드 호제법

-a를 b로 나눈 나머지를 r이라고 했을 때,

gcd(a,b)=gcd(b,r) 

-r이 0이면 그 때 b가 최대 공약수이다.

ex) gcd(24,16)

gcd(24,16)=gcd(16,8)=gcd(8,0)=8

(코드)

-재귀 함수 사용

int gcd(int a, int b){

if(b==0)

return a;

else{

return gcd(b,a%b);

}

}

-재귀 함수 미사용

int gcd(int a, int b){

while(b!=0){

int r = a%b;

a=b;

b=r;

}

return a;

}

3. 세 수의 최대공약수

gcd(a,b,c) = gcd(gcd(a,b),c)

-네 수, N개의 숫자도 위와 같은 식으로 계속해서 구할 수 있다.