[Algorithm] 유클리드 호제법
in Algorithm
Elice Algorithm Code Challenge - Day 2 (유클리드 호제법)
목차
유클리드 호제법
- 두 수가 서로 상대방 수를 나누어 원하는 수를 구하는 것
- GCD (Greatest Common Divisor) 최대공약수
- 두 자연수 a, b에 대해서 (a > b) a를 b로 나눈 나머지를 r이라고 하면
- a와 b의 최대공약수는 b와 r의 최대공약수와 동일
- 이 성질에 따라, b를 r로 나눈 나머지 r’를 구하고,
- 다시 r을 r’로 나눈 나머지를 구하는 과정을 반복하여 나머지가 0이 되었을때 나누는 수가 a와 b의 최대공약수
- 예시
- 1071과 1029의 최대공약수 구하기
- 1071 % 1029 = 42
- 1029 % 42 = 21
- 42 % 21 = 0
- 21이 1071과 1029의 최대공약수
- 1071과 1029의 최대공약수 구하기
- 두 자연수 a, b에 대해서 (a > b) a를 b로 나눈 나머지를 r이라고 하면
- LCM (Least Common Multiple) 최소공배수
- LCM(a, b) = a * b / GCD(a, b)
- 어떠한 두 수의 곱은, 그 두 수의 최대공약수와 최소공배수의 곱과 같다
- cpp의 gcd, lcm 함수는 c++17부터 지원
- numeric 모듈
- 보통 코테에서 c++17 사용
- python은 math 모듈의 gcd, lcm 함수
- gcd는 python 3.5
- lcm은 python 3.9
- 보통 코테에서 python 3.8 사용
- java는 지원하지 않음
소수 판별법
- 1은 소수, 합성수 아님
- 에라토스테네스의 체
- O(Nlog(logN))
- N이 커지면 거의 O(N)
- 회귀가 아닌 반복
- O(Nlog(logN))