섹션 5. 정수론

소수 구하기

소수(prime number)은 1과 자기 자신 외에 약수가 존재하지 않는 수이다.

소수를 구하는 대표적인 판별법은 에라토스테네스의 채가 있다.

1. 구하고자 하는 소수의 범위만큼 1차원 배열 생성
2. 2부터 시작하고 현재 숫자가 지워지지 않을 때는 현재 선택된 숫자의 배수에 해당하는 수를 배열에서 끝까지 탐색하면서 지운다. 이때 처음으로 선택된 숫자는 지우지 않는다. ← 소수
3. 배열의 끝까지 2번 과정을 반복한 후 배열에서 남아 있는 모든 수를 출력한다.

에라토스테네스의 체를 사용하는 경우 시간 복잡도

 

일반적으로 에라토스테네스의 체를 구현하기 위해 이중 for문을 사용하므로 O(n^2)으로 판단 할 수 있다. 하지만 실제 시간 복잡도는 O(nlog(logn))이다. 배수를 삭제하는 연산으로 실제 구현에서 바깥쪽 for문을 생략하는 경우가 빈번하게 발생하기 때문이다.

 

ex) 거의 소수 구하기 (백준 1456)

1. 문제 분석하기
   1. 최대 범위에 해당하는 모든 소수를 구해 놓기
   2. 이 소수들의 N 제곱값(거의 소수)가 입력된 A와 B 사이에 존재하는지 판단
   3. 입력에서 주어진 범위의 최댓값 10^14의 제곱근인 10^7까지 소수를 탐색
   4. N 제곱값을 구하는 도중 변수 표현 범위를 초과하는 경우 주의
      1. 이항정리 이용 N^k와 B가 아닌 N과 B / N^k-1을 비교

#include<iostream>
#include<cmath>

using namespace std;

long a[10000001];

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	long min, max;

	cin >> min >> max;

	for (int i = 2; i < 10000001; i++) {
		a[i] = i;
	}

	for (int i = 2; i <= sqrt(10000001); i++) {
		if (a[i] == 0) {
			continue;
		}
		for (int j = i + i; j < 10000001; j = j + i) {
			a[j] = 0;
		}
	}

	int count = 0;

	for (int i = 2; i < 10000001; i++) {
		if (a[i] != 0) {
			long temp = a[i];
			while ((double)a[i] <= (double)max / (double)temp) {
				if ((double)a[i] >= (double)min / (double)temp) {
					count++;
				}
				temp *= a[i];
			}
		}
	}
	cout << count << "\n";
}

오일러의 피

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

 

ex) P[6] = 2 ←(1,5)

1~6 중 6과 서로소인 수의 개수는 2개로 1과 5가 있다.

 

오일러 피 함수의 원리

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

ex) 오일러 피 함수 구현하기 (백준 11689)

1. 문제 분석
   1. GCD(n, k) = 1 → 두수의 최대공약수가 1인거 → 서로소 → 1~N 사이의 오일러피 함수
   2. 서로소의 개수를 표현하는 변수 result, 현재 소인수 구성을 표시하는 변수 n 선언
   3. result = result - (result / 소인수) 연산으로 result 값 업데이트
   4. 반복문 종료 후 현재 n이 1보다 크면 n이 마지막 소인수
   5. result값을 마지막으로 업데이트 한 후 출력

#include<iostream>
#include<vector>
#include<cmath>

using namespace std;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	long n;

	cin >> n;

	long result = n;

	for (long p = 2; p <= sqrt(n); p++) {
		if (n % p == 0) {
			result = result - result / p;
			while (n % p == 0) {
				n = n / p;
			}
		}
	}

	if (n > 1) {
		result = result - result / n;
	}
	cout << result << "\n";
}

유클리드 호제법

유클리도 호제법(euclidean-algorithm)은 두 수의 최대 공약수를 구하는 알고리즘이다.

최대 공약수를 구하는 방법은 소인수 분해를 이용한 공통된 소수들의 곱으로 표현할 수 있지만 유클리드 호제법은 더 간단한 방법을 제시

 

유클리드 호제법을 수행하기 위해 MOD연산을 이해 해야 한다. MOD 연산이 최대 공약수를 구하는데 사용된다.

 

Tip) MOD연산은 두 값을 나눈 나머지를 구하는 연산이다.

      ex) 10 % 4 = 2

 

MOD 연산으로 구현하는 유클리드 호제법

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

재귀형태로 쉽게 구현 한다.