Algorithm/Number Theory1 유클리드 호제법(Euclidean Algorithm) 최대공약수 구할 때 사용하는 유클리드 호제법에 대해서 남기려고 한다. 최대공약수 GCD(Greatest Common Divisor) 최소공배수 LCM(Least Common Multiple) 두 수가 작은 수라면 소인수분해를 통해서 gcd와 lcm을 구할 수 있지만 숫자가 크다면 다른 방식으로 구해야한다. 유클리드 알고리즘이란 2개의 자연수(a,b)의 최대공약수를 구하는데 "자연수 a, b가 있을 때 (a>b, a!=b) a를 b로 나눈 목을 q 나머지를 r이라고 했을 때 a = qb+ r이다. GCD(a,b) = GCD(b,r)이며 r이 0일 때 b가 최대공약수이다." 만약 r=0이 아니면 a에는 b를 b에는 r을 넣어서 r=0이 나올 때까지 반복한다. 라는 원리이다. 그림으로 표현해보겠다. mod연산.. 2022. 11. 28. 이전 1 다음 728x90 반응형
