[Algorithm] 유클리드 호제법

Elice Algorithm Code Challenge - Day 2 (유클리드 호제법)

목차

  1. 유클리드 호제법
  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의 최대공약수
  • 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)
    • Full-width image
    • 회귀가 아닌 반복