정수의 소인수분해 알고리즘

정수 K를 소인수분해하여 다음과 같이 나타낼 수 있다.
$K = p_{1}^{q_{1}}\times p_{2}^{q_{2}}...\times p_{i}^{q_{i}}\times M$

이때, $p_{1}, p_{2} ... p_{i} \leq \sqrt{K}$ 이고, M은 소수이다.

int K;
vector <pair<int, int>> primeFact;

int main(void) {
	cin >> K;
	for (int i = 2; i * i <= K; i++) {
		if (K % i == 0) {
			int p = i;
			int q = 0;
			while (1) {
				if (K % p == 0) {
					q++;
					K /= p;
				}
				else break;
			}	
			primeFact.push_back({ p,q });
		}
	}
	if(K != 1) primeFact.push_back({ K,1 });
	return 0;
}

위와 같은 코드로 p와 q를 저장할 수 있다.

 

만약 K의 범위를 알고 있다면, 미리 K 이하의 소수를 전처리하는 방법으로 시간 복잡도를 개선할 수 있다.

// K가 N이하의 수일 때
int K;
int table[N + 1];
vector <int> primeNum;

vector <pair<int, int>> primeFact;

int main(void) {
	for (int i = 2; i * i <= N; i++) {
		if (table[i] == 0) {
			table[i] = 1;
			primeNum.push_back(i);
			for (int j = i * i; j * j <= N; j += i) table[j] = 1;
		}
	}
	cin >> K;
	for (int i = 0; i < primeNum.size(); i++) {
		if (K < primeNum[i]) break;
		if (K % primeNum[i] == 0) {
			int p = primeNum[i];
			int q = 0;
			while (1) {
				if (K % primeNum[i] == 0) {
					q++;
					K /= primeNum[i];
				}
				else break;
			}
			primeFact.push_back({ primeNum[i],q });
		}
	}
	if(K != 1) primeFact.push_back({ K,1 });
	return 0;
}