[TIL] - 2022-04-08

1. 알고리즘
   유클리드 호제법

   1. 입력으로 두 수 m,n(m>n)이 들어온다.
   2. n이 0이라면, m을 출력하고 알고리즘을 종료한다.
   3. m이 n으로 나누어 떨어지면, n을 출력하고 알고리즘을 종료한다.
      그렇지 않으면, m을 n으로 나눈 나머지를 새롭게 m에 대입하고, m과 n을 바꾸고 3번으로 돌아온다.

def gcd(n1, n2):
    if n1 < n2:
        (n1, n2) = (n2, n1)
    while n2 != 0:
        (n1, n2) = (n2, n1 % n2)
    return n1

최대공약수는 N*M / 최소공배수

gcd 쓰면 편하게 가능

• 일정 범위에서 소수를 구할때는 에라토스테네스의 체를 사용

1. 2부터 N까지 존재하는 모든 자연수를 나열한다.

2. 나열된 숫자 중에서 가장 작은 수를 x로 지정한다.

3. 나열된 숫자 중에서 x의 배수를 모두 제거한다. (이때, x는 제거하지 않는다)

4. 더 이상 반복할 수 없을 때까지 2번과 3번을 반복한다.