A 와 B 가 서로소이면 A-B 와 B 는 서로소 이다
내 밥벌이 :
2007/05/16 17:58
A 와 B 가 서로소이면 A-B 와 B 는 서로소이다.
이말은 유클리드 알고리즘(최대공약수)를 읽다보면 나온는 말이다.
어제 글에 노력했더니 사람들이 천재라고 불렀다 라고 했는데.
최대공약수는 저런 단순한 알고리즘이지만, 그래도 참 똑똑한 녀석들은 그 이유가 있는 듯하다.
즉 B 와 A-B 의 최대공약수는 G 라는 말이 된다.
이런식을 계속 적용하여 A-B 의 값이 0 이 되면 a 또는 b 가 두 수의 최대공약수가 된다.
그렇다면, 우리가 어릴 때 배운 숫자 두개써넣고 줄긋고 찾아내는 최대공약수 풀이법보다 더 쉽게 최대 공약수를 생각해 볼 수 도 있다.
좀 더 나아가 A-B 를 계속 한다는 것은 A 를 B 로 나눈 나머지를 찾아내는 일이 기 때문에 A-B 를 A%B 로 바꾸면 식은 더 간단해 질 것이다.
코드로 나타내면 아래와 같을 것이다.
물론 읽고 나면 간단하다.
과연 저런 것을 첨에 생각해내는 사람들???
나도 매일매일 노력하면 저런생각을 해낼 수 있는 것일까??
이말은 유클리드 알고리즘(최대공약수)를 읽다보면 나온는 말이다.
어제 글에 노력했더니 사람들이 천재라고 불렀다 라고 했는데.
최대공약수는 저런 단순한 알고리즘이지만, 그래도 참 똑똑한 녀석들은 그 이유가 있는 듯하다.
A = a * G
B = b * G 이라면 A-B = (a-b) * G 이다.
즉 B 와 A-B 의 최대공약수는 G 라는 말이 된다.
이런식을 계속 적용하여 A-B 의 값이 0 이 되면 a 또는 b 가 두 수의 최대공약수가 된다.
그렇다면, 우리가 어릴 때 배운 숫자 두개써넣고 줄긋고 찾아내는 최대공약수 풀이법보다 더 쉽게 최대 공약수를 생각해 볼 수 도 있다.
좀 더 나아가 A-B 를 계속 한다는 것은 A 를 B 로 나눈 나머지를 찾아내는 일이 기 때문에 A-B 를 A%B 로 바꾸면 식은 더 간단해 질 것이다.
코드로 나타내면 아래와 같을 것이다.
int euclidMethod(int a, int b)
{
int t;
while(b != 0)
{
t = a % b;
a = b;
b = t;
}
return a;
}
{
int t;
while(b != 0)
{
t = a % b;
a = b;
b = t;
}
return a;
}
물론 읽고 나면 간단하다.
과연 저런 것을 첨에 생각해내는 사람들???
나도 매일매일 노력하면 저런생각을 해낼 수 있는 것일까??
'내 밥벌이' 카테고리의 다른 글
| 엠파스 와 네이버 (0) | 2007/06/20 |
|---|---|
| A 와 B 가 서로소이면 A-B 와 B 는 서로소 이다 (0) | 2007/05/16 |
| 최대 쓰레드라.. (0) | 2007/03/12 |
| TCP State Diagram (0) | 2007/03/03 |
