유클리드 알고리즘

유클리드 알고리즘

유클리드 알고리즘💡두 수의 최대공약수를 구하는 방법정의두 수 p, q(p>q)의 공약수 집합은 p-q와 q의 공약수 집합과 같다. 증명p, q의 공약수 g가 존재한다고 해보자그럼 다음과 같이 나타낼 수 있다.p = p’gq = q’g 이때 p-q = (p’ - q’)g 이므로g는 p-q의 약수이며, q의 약수이다. 구현위를 이용하여 코드로 구현해보자int gcd(int p, int q) { if (p < q) { int tmp = q; q = p; p = tmp; } if (q == 0) { return p; } return gcd(p - q, q); }짧은 코드로 구현이 가능하나, 위 코드를 보면 p와 q의 차이가 클 경우에 많은 연산이 이루어 질 수 있다는 단점이 있다.gcd(1024,6)=gcd(1..