[BOJ/Silver 1] 백준 1124 언더프라임(C++)

문제 링크

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

 

문제

자연수 X를 소인수분해하면, 곱해서 X가 되는 소수의 목록을 얻을 수 있다. 예를 들어, 12 = 2 × 2 × 3이다. 1은 소수가 아니다.

어떤 수 X를 소인수분해 해서 구한 소수의 목록의 길이가 소수이면, 그 수를 언더프라임 이라고 한다. 12는 목록에 포함된 소수의 개수가 3개이고, 3은 소수이니 12는 언더프라임이다.

두 정수 A와 B가 주어졌을 때, A보다 크거나 같고, B보다 작거나 같은 정수 중에서 언더프라임인 것의 개수를 구해보자.

 

입력

첫째 줄에 두 정수 A와 B가 주어진다.

 

출력

첫째 줄에 A보다 크거나 같고, B보다 작거나 같은 언더프라임 개수를 출력한다.

 

제한

• 2 ≤ A ≤ B ≤ 100,000

 

예제 입력 1

2 10

예제 출력 1

5

예제 입력 2

100 105

예제 출력 2

2

예제 입력 3

17 17

예제 출력 3

1

예제 입력 4

123 456

예제 출력 4

217

 

알고리즘 분류

• 소수 판정

 

풀이

소인수분해 후 구한 소수 목록의 길이를 UP[100000]라고 하자.

처음에 2부터 100,000까지 UP들은 전부 1이라고 한다.

에라토스테네스의 체를 활용해서 각 수들의 UP의 값을 갱신한다.

마지막으로 A, B를 입력받고 A부터 B까지 소수 목록의 길이 수치가 소수인 수들의 개수를 구한다.

 

코드

#include <iostream>
#include <vector>
#include <string>
#include <cmath>
#include <algorithm>
#define MAX 100001
#define FASTIO cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);

using namespace std;
int A, B;
int DP[MAX], UP[MAX];
int Answer;

void init() {
	for (int i = 2; i < MAX; i++) {
		DP[i] = i;
		UP[i] = 1;
	}
	for (int i = 2; i <= sqrt(MAX); i++) {
		if (DP[i] == 0) continue;
		UP[i] = 1;
		int Count = 0;
		for (int j = (i * i); j < MAX; j += i) {
			DP[j] = 0;
			UP[j] = UP[j / i] + 1;
		}
	}
}

void input() {
	cin >> A >> B;
}

void settings() {
	for (int i = A; i <= B; i++) {
		if (DP[UP[i]] != 0) Answer++;
	}
}

void find_Answer() {
	cout << Answer << "\n";
}

int main() {
	FASTIO
	init();
	input();
	settings();
	find_Answer();

	return 0;
}