정수론

소수 구하기

소수란?

• 소수는 자신보다 작은 2개의 자연수를 곱해 만들 수 없는 1보다 큰 자연수(== 1과 자기 자신 외에 약수가 존재하지 않는 수)

소수 구하기의 핵심 이론

• 소수를 구하는 대표적인 판별법으로는 에라토스테네스의 체가 있음

에라토스테네스의 체 원리

1. 구하고자 하는 소수의 범위만큼 1차원 배열을 생성

2. 2부터 시작하고 현재 숫자가 지워지지 않을 때는 현재 선택된 숫자의 배수에 해당하는 수를 배열에서 끝까지 탐색하면서 지움(이때 처음으로 선택된 숫자는 지우지 않음)

3. 배열의 끝까지 2를 반복한 후 남아 있는 모든 수를 출력

• 일반적으로 에라토스테네스의 체를 구현하려면 이중 for문을 이용하므로 시간 복잡도가 O(N²) 정도라고 판단
• 하지만 실제 시간 복잡도는 최적화의 정도에 따라 다르지만, 일반적으로 O(Nlog(logN))
• 배수를 삭제하는 연산으로 실제 구현에서 바깥쪽 for문을 생략하는 경우가 빈번하게 발생

오일러 피

오일러 피란?

• 오일러 피 함수 P[N]의 정의는 1부터 N까지 범위에서 N과 서로소인 자연수의 개수를 뜻함

오일러 피의 핵심 이론

1. 구하고자 하는 오일러 피의 범위만큼 배열을 자기 자신의 인덱스값으로 초기화
2. 2부터 시작해 현재 배열의 값과 인덱스가 같으면(== 소수일 때) 현재 선택된 숫자(K)의 배수에 해당하는 수를 배열에 끝까지 탐색하며 P[i] = P[i] / K 연산을 수행(i는 K의 배수)
3. 배열의 끝까지 2를 반복하여 오일러 피 함수를 완성

예시

• 초기 상태 : ∮(6) = 6 -> 서로소가 될 수 있는 후보의 개수로 초기화(1, 2, 3, 4, 5, 6)
• 2의 배수로 인한 탈락 -> ∮(6) = 6 - (6 / 2) = 3(1, 3, 5)
• 3의 배수로 인한 탈락 -> ∮(6) = 3 - (3 / 3) = 2(1, 5)

이때 후보에서 삭제하는 기준을 6이 아닌 업데이트된 3으로 진행하는 이유는 3의 배수 중 2의 배수인 수는, 즉, 3과 2의 공배수는 2의 배수에서 이미 삭제됐기 때문에 중복 삭제를 막기 위함

서로소란? 여러 개의 수들 사이에서 1 이외의 공약수가 없음을 이르는 말

유클리드 호제법

유클리드 호제법이란?

• 두 수의 최대 공약수를 구하는 알고리즘
• 일반적으로 최대 공약수를 구하는 방법은 소인수 분해를 이용한 공통된 소수들의 곱으로 표현할 수 있지만 유클리드 호제법은 좀 더 간단

유클리드 호제법의 핵심 이론

• 먼저 MOD 연산을 이해해야 함

  MOD 연산 : 두 값을 나눈 나머지를 구하는 연산 (ex: 10 MOD 4 = 2)

1. 큰 수를 작은 수로 나누는 MOD 연산을 수행
2. 앞 단계에서 작은 수와 MOD 연산 결괏값(나머지)으로 MOD 연산을 수행
3. 2를 반복하다가 나머지가 0이 되는 순간의 작은 수를 최대 공약수로 선택