최대공약수 구하는 함수 질문입니다.
연블루
2023.04.01
질문 제목 : 최대공약수 구하는 함수 질문입니다.최대공약수 구하는 함수 질문입니다.질문 내용 : 최대공약수 구하는 함수 질문입니다.
아래 방식(?)대로 최대공약수를 구해야 하는데, 복잡해서 잘 모르겠습니다.
이렇게 설명되어 있으니 더 어렵네요.ㅜ.ㅜ 좀 알려주세요.
- int find_gcd(int n1, int n2)
정수 n1과 n2의 최대공약수를 구하는 함수. 다음은 최대 공약수를 구하는 알고리즘이다. (순환함수를 이용하여 구현해서는 안된다. 순환함수는 가르쳐준 적이 없다.)
① n1의 절대값을 q에 n2의 p절대값을 에 넣는다.
② q를 p로 나눈 나머지를 r에 저장한다.
③ r이 0이 아니면 ④로 r이 0이면 ⑦로 간다.
④ p를 q로 옮기고 r을 p로 옮긴다.
⑤ q를 p로 나눈 나머지를 r에 저장한다.
⑥ ③으로 간다.
⑦ p는 최대 공약수이다.
-
매1혻적
감사합니다. 그런식으로 하면 되는거 였군요. 다른 쉬운 방법도 있을텐데, 저거대로 할려니까 어려워서요.
-
핑1크캣
#define ABS(x) ((x0)?(-x):(x))
int q = ABS(n1);
int p = ABS(n2);
int r = q%p;
while(1)
{
if ( r != 0 ) { q = p; p = r; r = q%p; }
else { return p }
}
//(1)~(7)을 그대로 쓴거에요