백준 1124번 C++

백준 1124번 언더프라임
https://www.acmicpc.net/problem/1124

1124번: 언더프라임

정답 코드

#include<iostream>
#include<math.h>
using namespace std;
int arr[100001] = { 1,1 };
void prime() {
	for (int x = 2; x <= sqrt(100001); x++) {
		for (int y = x * x; y <= 100001; y += x) {
			if (arr[y] != 0)
				continue;
			else
				arr[y] = 1;
		}
	}
}
int abc(int a) {
	int count = 0;
	for (int x = 2; x <= a; x++) {
		if (arr[x]==0&&a % x == 0) {
			a /= x;
			count++;
			x--;
		}
		if (a == 1)
			break;
	}
	return count;
}
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int a, b;
	cin >> a >> b;
	prime();
	int sum = 0;
	for (int x = a; x <= b; x++) {
		int d = abc(x);
		if (arr[d] == 0)
			sum++;
	}
	cout << sum;
}

문제 풀이
언더프라임에 관한 문제입니다. 언더프라임이란, 어떤  수 N을 소인수분해하여 얻은 소수의 갯수가 소수인 것을 말합니다. 여기서는 에라토스테네스의 체를 이용해서 먼저 소수를 구하여야 합니다. 일반적인 방식으로 구할 시에는 시간복잡도가 더 커지기 때문에 시간초과가 뜹니다. 그 후 입력받은 수를 소수로 나눠주고 그 갯수가 소수인지 판정만 하면 쉽게 풀 수 있습니다.