백준 1456. 거의 소수

거의 소수

간단한 소수 문제인줄 알았으나, 오버플로우 처리 문제였음

1. 간단 설명

---

거의 소수 = 소수를 N제곱 한 수들의 집합임

2의 거의 소수들 = 4 8 16 ...
3의 거의 소수들 = 9 27 81 ...
4의 거의 소수들 = 16 64 ...
5의 거의 소수들 = 25 125 ...

이런식으로 소수 2의 2제곱, 3제곱, 4제곱 한 수들, 소수 3의 2제곱, 3제곱 등등

A와 B가 주어질 때, 해당 범위 내의 ‘거의 소수’의 개수를 찾는 문제

2. 예제

---

1 10

1<= x <= 10을 만족하는 거의 소수는

2의 2제곱, 3제곱 (4, 8)과 3의 2제곱 (9) 총 3개다

3. 알고리즘

---

1. 거의 소수를 모두 구해본다

즉, 소수를 모두 구하고, 모두 제곱해봐서 A와 B 사이에 속하는지 체크해본다

근데 A와 B의 범위가 최대 10^14이므로 너무 많은 수를 처리해야하므로 불가능해 보인다

이를 위해 다른 방법이 필요

1. 에라토스테네스의 체를 이용해 소수를 구하고, 얘내의 ‘거의 소수’들이 속하는지 판별

먼저 A부터 ‘어느 수’까지의 소수를 구한 뒤에

이 소수의 ‘거의 소수’들이 A, B 사이인지 확인해본다

‘어느 수’는 몇 정도 되는게 적당할까?

B의 최대값이 10^14 이므로, B의 제곱근인 10^7, 100만까지 구해본다

100만까지의 소수를 구하는 과정은 충분히 처리 가능

1. A, B 입력받기
2. 에라토스테네스의 체를 이용해 100만까지의 소수 구하기
3. 이 소수들의 '거의 소수'들이 A, B 사이에 속하는지 체크하기

4. 소스코드

---

#include <iostream>
#include <algorithm>
#include <math.h>

#define MAX 10000001

using namespace std;

bool isPrime[MAX];

int main() {
	unsigned long long int A, B;
	cin >> A >> B;

	// 소수 판별
	fill(isPrime, isPrime + MAX, true);
	
	// 에라토스테네스의 체로 소수 구하기
	for (int i = 2; i < MAX; i++) {
		if (isPrime[i] == false) continue;
		for (int j = i * 2; j < MAX; j = j + i) {
			isPrime[j] = false;
		}
	}

	// 거의 소수 개수 체크
	int ans = 0;

	// 2부터 sqrt(B)까지 체크
	for (unsigned long long i = 2; i <= sqrt(B); i++) {
		if (isPrime[i]) { // 해당 수가 소수라면
			unsigned long long power = i * i;

			while (power <= B) {
				// A보다 크고, B보다 작은경우
				if (power >= A) {
					ans++;
				}
				if (power > B / i) { // 곱셈 오버플로우 방지를 위해서 나눗셈으로 연산
					// power * i > B 인지 체크. 더 크다면 더 이상 연산하지 않음
					break;
				}
				power *= i;
			}
		}
	}
	cout << ans;

	return 0;
}

연산 중에 10^21 이상을 체크할 필요가 있다

이를 위해서 별도로 power 지수를 두고, 이 수가 B를 넘어가는지를 체크해야 오버플로우가 발생하지 않는다

power * i > B 는 power > B / i 와 같으므로 이를 이용해서

unsigned long long 으로 처리 가능한 수로 다뤄줬다

소수 판별이나 거의 소수는 쉬웠으나 이 부분이 가장 햇갈렸다