목록최대공약수 (1)

개발정리

유클리드 호제법

유클리드 호제법이란?두수의 '최대 공약수'를 찾기 위한 알고리즘두개의 자연수에 대하여 (a>b)일때 a를 b로 나눈 나머지를 r이라고 했을때GCD(a,b) = GCD(b,r) 이라는 수식을 만족하며r=0일때 그때 b값이 최대공약수 입니다. 자바코드int gcd(int a , int b){ while(b != 0){ int r = a%b; a=b; b=r; } return a;}- while문사용 int GCD(int a,int b){ if(a%b == 0){ return b; } return GCD(b,a%b); }-재귀함수 사용
CS/알고리즘 2024. 7. 8. 14:39
이전 Prev 1 Next 다음