[BOJ] 1124 : 언더프라임 - travelbeeee

문제 : https://www.acmicpc.net/problem/1124

---

[ 알고리즘풀이 ]

 에라토스테네스체 + DP 를 이용해서 문제를 해결할 수 있습니다.

1. 에라토스테네스체를 이용해서 100,000 이하의 모든 소수를 check 합니다.

2.  DP[i] : 소인수 분해했을 때 나오는 소수의 개수. 라고 정의

→ i를 나누는 가장 작은 소수 j에 대해서 DP[i] = DP[i / j] + 1 이 성립합니다.

이 방정식을 이용해서 DP 배열을 채울 수 있습니다. 이때, i가 소수면 DP[i] = 1이 되므로, (1) 에라토스테네스체를 채워가는 과정에서 소수에 대해서만 DP[i] = 1로 초깃값을 줍니다. 

3. A ~ B 까지 순회하며 DP 값이 소수인 애들을 count 해줍니다.

#include<iostream>

using namespace std;

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

	int A, B, ans = 0, dp[100001] = {};
	bool prime[100001] = {};

	prime[0] = true, prime[1] = true;

	for (int i = 2; i <= 100000; i++) {
		if (prime[i] == false) {
			dp[i] = 1;
			for (int j = 2 * i; j <= 100000; j += i)
				prime[j] = true;
		}
	}

	cin >> A >> B;

	for (int i = 2; i <= B; i++) {
		if (dp[i] == 0) {
			for (int j = 2; ; j++) {
				if (i % j == 0){
					dp[i] = dp[i / j] + 1;
					break;
				}
			}
		}
	}

	for (int i = A; i <= B; i++) {
		if (prime[dp[i]] == false)
			ans++;
	}

	cout << ans;
}

---