[정수론] 소수

에라토스테네스의 체

vector<bool> isPrime(N+1, true);
isPrime[0] = isPrime[1] = false;
for (int i=2; i<= sqrt(N); ++i) {
	if (isPrime[i]) {
    	for (int temp = i*i; temp<=N; temp+= i)
        	isPrime[temp] = false;
    }
}

중요한 포인트가 두개 있다. sqrt(n)까지만 탐색하는 것과, 소수 p를 발견하고 n까지 p의 배수들을 지울 때, p*p부터 시작한다는 점이다.

sqrt(n)까지만 봐도 되는 이유는, isPrime의 기본값이 true이기 때문이다. 따라서 우리는 합성수들에 대해 isPrime의 값을 전부 false로 처리했다고 보장할 수 있으면 탐색을 종료하는 최적화가 가능하다.
sqrt(n)보다 크고 N이하인 합성수들은 sqrt(n)보다 작은 소인수를 반드시 가진다. 따라서 이미 sqrt(n) 이전의 소수에 의해 합성수로 처리되었음을 보장할 수 있다.

또한 소수 p에 대해서, p보다 작은 소수들의 배수들은 이미 지워졌기 때문에, p*2가 아니라 p*p부터 탐색하면 된다.

소인수 분해

vector<int> primeFactorization(int n) {
	vector<int> ret;
    for (int i=2; i<=sqrt(n); ++i) {
    	while (n%i==0) {
        	ret.push_back(i);
            n/=i;
       	}
    }
    if (n >1)
    	ret.push_back(n);
    return ret;
}

i가 소수인지 합성수인지 체크할 필요가 없다. i가 합성수라면, i의 소인수들은 i보다 작으므로 이미 n에서 나눠졌기 때문에 while문이 실행되지 않는다. 그리고 sqrt(n)까지만 탐색했는데, sqrt(n)보다 큰 소인수는 기껏해야 하나만 존재함을 귀류법으로 쉽게 증명할 수 있고, 그 소인수는 남아있는 n임을 알 수 있다.

위 알고리즘을 에라토스테네스의 체로 전처리를 하면, 소수들만 탐색하도록 최적화할 수 있다.

소수 판별

bool isPrime(int n) {
	if (n<=2) {
    	// 따로 처리
    }
    if (n%2==0)
    	return false;
    for (int i=3; i<=sqrt(n); ++i) 
    	if (n%i == 0)
        	return false;
    return true;
}

마찬가지로 에라토스테네스의 체를 이용하면 최적화할 수 있다.

소인수 분해 (최적화버전)

//isPrime 대신 다른방식으로 소수를 판별한다
//[i] : i의 소인수중 가장 작은 소인수
//[i] = i로 초기화해두고, [i] == i면 소수로 판단
int minFactor[N+1];
minFactor[1] = -1; // 예외

// 에라토스테네스의 체 전처리
for (int i=2; i<= sqrt(N); ++i) {
	if (minFactor[i] == i) {
    	for (int temp = i*i; temp<=N; temp+= i)
        	if (minFactor[temp] = temp)
            	minFactor[temp] = i;
    }
}

vector<int> optimizedPrimeFactorization(int n) {
	vector<int> ret;
    while (n>1) {
    	ret.push_back(minFactor[n]);
        n /= minFactor[n];
    }
}

흥미롭다.

참고 ) 종만북