PS를 위한 정수론 - (1) 에라토스테네스의 체 활용

 

기본적인 '에라토스테네스의 체' 개념을 아직 모른다면 wogud6792.tistory.com/46 글을 먼저 읽는 것을 추천한다.

크게 어렵지는 않다. 

 

그렇다면 이제 이 에라토스테네스의 체를 활용하는 여러 가지 방법들을 알아보자. 

 

  1. 각 2부터 n까지의 자연수 k에 대해, "k가 갖는 가장 작은 소인수"를 계산하는 방법

 

이는 사실 매우 간단하다. 

에라토스테네스의 체 원리를 생각해보면 현재 수가 아직 걸러지지 않았다면 소수이고, 현재 수의 배수들을 제거해나가는 방식이다. 

이때, 제거되는 수는 합성수이고 제일 처음 제거될 때 이용되는 소수가 $k$가 갖는 가장 작은 소인수이다.

 

int prime[1000001];
int main(void) {
	int N = 1000000;
	for (int i = 1; i <= N; i++) prime[i] = i;
	for (int i = 2; i <= N; i++) {
		if (prime[i] == i) { //아직 걸러지지 않았다는 의미 == i는 소수
			for (int j = 2; j*i <= N; j++) {
				if (prime[i*j] == i*j) prime[i*j] = i;
			}
		}
	}
}

 

코드를 통해서도 알 수 있듯이 기존에는 소수인지 아닌지만 체크하던 prime배열에

boolean값이 아니라 가장 작은 소인수를 넣어주기만 하면 된다. 

 

 

  2. 각 2부터 n까지의 자연수 k에 대해, "빠르게 k를 소인수분해" 하는 방법

 

자연수 $k$를 소인수분해를 하는 가장 기초적인 방법은 직접 $2$부터 $\sqrt{k}$ 까지 나눠주는 방법이다.

만약 현재 $k$가 $i$로 나누어 떨어지면 $i$로 더 이상 나누어 떨어지지 않을 때까지 나눠준다. 

나누어지는 횟수만큼 소인수 $i$가 $k$에 포함되어있는 것이다. 

$\sqrt{k}$까지 모두 나누어주었을 때, 아직 $k$가 $1$이 아니라면 이 또한 $\sqrt{k}$보다 큰 소수이며, 기존의 $k$의 소인수가 된다. 

 

하지만, 이 방식으로 $2$부터 $n$까지의 모든 자연수 $k$에 대해서 소인수분해를 한다면 $O(n\sqrt{n})$ 의 시간 복잡도를 가지게 된다. 

 

여기서 1번에서 설명한 $k$가 갖는 가장 작은 소인수를 이용하여 $O(nlogn)$ 만에 $2$부터 $n$까지의 모든 자연수를 소인수분해 할 수 있다. 

 

각 $2$부터 $n$까지 모든 자연수의 가장 작은 소인수를 전처리해두었다고 가정하자. 

그러면 자연수 $k$에서 시작해서, 가장 작은 소인수를 나누어주는 과정을 반복하면 소인수분해가 완성된다. 

여기서 가장 작은 소인수는 항상 $2$이상이므로 $O(logk)$안에 가능하다. 

 

int prime[1000001];
vector<int> fac[1000001];
int main(void) {
	int N = 1000000;
	for (int i = 1; i <= N; i++) prime[i] = i;
	for (int i = 2; i <= N; i++) {
		if (prime[i] == i) {
			for (int j = 2; j*i <= N; j++) {
				if (prime[i*j] == i*j) prime[i*j] = i;
			}
		}
	}
	for (int i = 2; i <= N; i++) {
		int k = i;
		while (k > 1) {
			fac[i].push_back(prime[k]);
			k /= prime[k];
		}
	}
}

 

 

  3. 각 2부터 n까지의 자연수 k에 대해 "k의 약수의 개수" 빠르게 구하는 방법

 

만약 약수의 개수를 구하는 경우에는 완전히 소인수분해를 하지 않고 더 빠르게 해결할 수 있다. 

$k$의 약수의 수를 구하기 위해서 $k-1$ 이하의 모든 자연수에 대해서 약수의 수를 알고 있다고 가정한다. 

아래의 예시는 종만북에 나와 있는 예시이다. 

 

$67500$의 약수를 구한다고 가정하자. $67500$을 소인수 분해하면 $2^2*3^3*5^4$ 로 나온다. 

따라서 $67500$의 약수의 수는 $3*4*5$ = $60$개다. ('지수 + 1'의 곱)

 

소인수 분해하지 않고 약수의 수를 구하기 위해서 $67500$의 가장 작은 약수인 2로 나누면 $33750$ = $2*3^3*5^4$를 얻을 수 있다. 

$33750$은 $2*4*5$ = $40$개의 약수가 있는데, 여기서 $2$를 $3$으로 바꾼 값이 $67500$의 약수의 수가 된다. 

즉, $33750$의 약수의 수를 이미 알고 있다면, 여기에 $3/2$를 곱해서 바로 $67500$의 약수의 수를 얻을 수 있는 것이다. 

 

일반화하면 다음과 같다. 

 

$n$의 약수의 개수를 $fac(n)$이라고 하자.

$k$의 가장 작은 소인수가 $p$이고, 이 소인수가 $k$에서 $a$번 출현한다면 $fac(k/p)*(a+1)/a$ = $fac(k)$ 를 만족한다. 

 

이 방식을 이용하면 1000만 이하의 모든 수에 대해서 약수의 수를 1초 안에 계산할 수 있다. 

 

int prime[1000001];
int fac[1000001];
int minfac[1000001]; //가장 작은 소인수의 출현 횟수
int main(void) {
	int N = 1000000;
	for (int i = 1; i <= N; i++) prime[i] = i;
	for (int i = 2; i <= N; i++) {
		if (prime[i] == i) {
			for (int j = 2; j*i <= N; j++) {
				if (prime[i*j] == i*j) prime[i*j] = i;
			}
		}
	}
	fac[1] = 1;
	for (int i = 2; i <= N; i++) {
		if (prime[i] == i) {
			fac[i] = 2;
            		minfac[i] = 1;
		}
		else {
			int p = prime[i]; //p == i의 가장 작은 소인수
			int m = i / p;
			if (p != prime[m]) { //m이 p로 더이상 나누어지지 않는 경우 == i가 p를 하나만 가지는 경우
				minfac[i] = 1;
			}
			else {
				minfac[i] = minfac[m] + 1;
			}
			int a = minfac[i];
			fac[i] = (fac[m] / a)*(a + 1);
		}
	}
}

 

위 방법은 꽤나 빠른 시간 안에 수행되지만 사실 이보다 시간은 더 걸리면서 매우 간단한 방식이 있다. 

에라토스테네스의 체를 수행하지 않고, 각 수의 약수를 직접적으로 구하는 것이다.

코드를 먼저 확인해보자.

 

int fac[1000001];
int main(void) {
	int N = 1000000;
	for (int i = 1; i <= N; i++) {
		for (int j = i; j <= N; j += i) {
			fac[j]++;
		}
	}
}

 

당장 코드만 보면 왜 이 방법을 진작에 설명해주지 않은 걸까 싶다.

하지만 이 방식은 시간 복잡도가 $O(nlogn)$이기 때문에 $n$이 1000만보다 커진다면 시간이 많이 걸리므로 $n$이 작은 경우에 이용하기 적당하다. 

 

시간 복잡도가 $O(nlogn)$인 이유는 다음과 같다.

우선 코드를 보면, 각 $i$에 대해서 내부에 있는 for문은 대략 $\frac{10^6} {i}$ 번 반복한다. 

따라서 전체 반복문의 수행 횟수는 아래의 식과 같다.

 

$\sum_{i=1}^{10^6} \frac{10^6}{i} = 10^6 \times  \sum_{i=1}^{10^6}  \frac{1}{i}$ 

 

이때, $10^6$에 곱해지는 급수는 조화 급수(harmonic series)로, 이 값은 $n$이 무한히 커지면 $ln(n)$에 수렴하게 된다.

증명은 간단하다 (stackoverflow.com/questions/25905118/finding-big-o-of-the-harmonic-series)

그러므로 시간 복잡도는 $O(nlogn)$에 수렴하게 된다. 

 

 

  4. A+1, A+2,... , A+n 각각이 소수인지 빠르게 판별하는 방법

 

앞에서 언급한 조화 급수의 성질에 의해서 $1$부터가 아닌 $A$부터 시작해도 $O(nlogn)$ 안에 판별할 수 있음을 알 수 있다.

$2$부터 $\sqrt{A+n}$까지의 수를 순서대로 체크하며, 현재 수를 $k$라고 하자. 

$A+1, ..., A+n$ 의 모든 수 중에서 $k$가 아닌 $k$의 배수를 모두 제거한다. 그러면 결국 소수만 남게 된다. 

이때, 각 $k$에 대해서 확인하는 수는 $O(n/k)$이고, $k$는 $2$부터 $\sqrt{A+n}$까지이므로 조화 급수의 성질에 의해 $O(nlogn)$ 임을 알 수 있다. 

그러므로 체크하는 범위까지 고려한다면 최종적으로 $O(\sqrt{A} + nlogn)$의 시간 복잡도를 갖는다. 

 

 

 

 

본 글은 rkm0959.tistory.com/ 블로그에서 도움을 받았습니다.

허락해주신 rkm0959님 감사드립니다.