소인수분해, 소수 판별법, 에라토스테네스의 체

 

소수: 1과 자기자신을 약수로 갖는 숫자

소인수분해: 어떤 정수 N 을 소수의 곱으로만 표현한 것

단순히 배수 판정법으로 문제를 해결할 수 있으나 숫자가 커질수록 시간복잡도가 너무 커져 비효율적이다.

위키에 따르면, 다음과 같은 정리가 성립한다고 한다.

3개 이상의 소수로 구성된  합성수는 그 수의 제곱근보다 작거나 같은 약수를 갖는다.

이에 대한 증명은 다음과 같다.

n 을 합성수라 하자. 그러면  n=ab 로 표현할 때, 1<a,b<n 이다.
만약  a,b 가 둘 다  n의 제곱근보다 크다면 [ a, b > sqrt(n) ]
ab > n 가 되어 n = ab 와 모순이다. 따라서  a,b 중 적어도 하나는 n의 제곱근보다 작거나 같다.

위의 증명때문에 1~N 사이의 숫자로 모두 나눠보지 않아도 N의 제곱근보다 작은 숫자만으로 소인수분해가 가능하다는 걸 알 수 있다.

해당 알고리즘은 for문을 2~sqrt(n) 번 돌리면서 나오는 약수의 소수를 찾아서 배열에 저장한다.

 

에라토스테네스의 체: 숫자 2부터 N까지 있으면, 각 숫자의 소수임을 판별할 때 배수가 되는 숫자들을 지워나가는 방법으로 속도가 빠르네 메모리 공간을 많이 차지하므로 비트마스크 등 별도의 최적화를 수행하기도 한다.

int n;
bool isPrime[MAX_N+1]; // 숫자 i의 소수 유무

void eratosthenes() {
	memset(isPrime, 1, sizeof(isPrime));
	// 1은 항상 예외 처리
	isPrime[0] = isPrime[1] = false;
	int sqrtn = int(sqrt(n)); // 어떤 약수도 sqrt(n) 을 넘기지 않음
	for (int i=2; i<=sqrtn; i++)
		if (isPrime(i)) // 이 수가 아직 지워지지 않았다면
			for (int j=i*i; j<=n; j+=i)
				isPrime[j] = false;
	// i의 배수 j에 대해 isPrime[j] = false;
	// i*i 미만의 배수들은 이미 처리됨. (2*i, 3*i 등 j=2,3일 때)
}

 

 

에라토스테네스의 체를 이용한 빠른 소인수 분해

// minFactor[i]: i의 가장 작은 소인수 저장 (i가 소수인 경우 자기 자신)
int minFactor[MAX_N];
// 에라토스테네스의 체를 수행하면서 소인수분해를 위한 정보도 저장
void eratosthenes2() {
	// 1은 항상 예외 처리
	minFactor[0] = minFactor[1] = -1;
	// 모든 숫자를 처음에는 소수로 표시
	for (int i=2; i<=n; i++)
		minFactor[i] = i;
	// 에라토스테네스의 체를 수행
	int sqrtn = int(sqrt(n));
	for (int i=2; i<=sqrtn; i++) {
		if (minFactor[i] == i)
			for (int j=i*i; j<=n; j+=i)
				if (minFactor[j] == j)
					minFactor[j] = i; // 아직 약수를 본 적 없는 숫자인 경우
	}
}

// 2이상의 자연수 n을 소인수분해한 결과를 반환
vector<int> factor(int n) {
	vector<int> ret;
	// n이 1이 될 때까지 가장 작은 소인수(minFactor)로 나누기를 반복한다.
	while (n > 1) {
		ret.push_back(minFactor[n]);
		n /= minFactor[n];
	}
	return ret;
}