(C++) baekjoon 1456 거의소수

문제
어떤 수가 소수의 N제곱(N ≥ 2) 꼴일 때, 그 수를 거의 소수라고 한다.

두 정수 A와 B가 주어지면, A보다 크거나 같고, B보다 작거나 같은 거의 소수가 몇 개인지 출력한다.

---

입력
첫째 줄에 왼쪽 범위 A와 오른쪽 범위 B가 공백 한 칸을 사이에 두고 주어진다.

---

출력
첫째 줄에 총 몇 개가 있는지 출력한다.

제한
1 ≤ A ≤ B ≤ 1014

---

예제 입력 1 

1 1000

예제 출력 1 

25

예제 입력 2 

1 10

예제 출력 2 

3

예제 입력 3 

5324 894739

예제 출력 3 

183

---

<code>

/*
2023_07_24
backjoon 1456_ 거의소수 https://www.acmicpc.net/problem/1456
*/
#include<iostream>
#include<cmath>
#define MAX 10000001
using namespace std;

int main() {
    long A, B;
    cin >> A >> B;
    long decimal[MAX];

    for (int i = 2; i < MAX; i++) { // 10^7까지의 배열 초기화
        decimal[i] = i;
    }

    for (int i = 2; i < sqrt(MAX); i++) { // 에라토스테네스 체 소수 구하기
        if (decimal[i] == 0) {
            continue;
        }
        for (int j = i + i; j < MAX; j += i) {
            decimal[j] = 0;
        }
    }

    // 거의소수 구하기
    int cnt = 0;
    for (int i = 2; i < MAX; i++) {
        if (decimal[i] != 0) {
            long temp = decimal[i];
            while ((double)temp <= (double)B / (double)decimal[i]) {
                if ((double)temp >= (double)A / (double)decimal[i]) {
                    cnt++;
                }
                temp *= decimal[i];
            }
        }
    }

    cout << cnt;
    return 0;
}

---

소수의 N제곱을 구하는 문제이다. 

입력 최대 범위인 10^14까지 구하게 된다면 너무 큰 수이므로 입력범위를 초과하게 된다.

소수의 제곱값이상을 구할것이므로 10^7까지만 구할것이다.

추가적으로 N제곱한 값을 구하는 도중 값이 변수 표현 범위를 초과하는 경우가 발생하는데, 이에 계산 오류를 방지하기위해 N^k와 B값이 아닌 N과 B /N^k-1을 비교하는 형식으로 식을 정리해서 표현했다.

문제 해설 참조는 다음을 참고했다.

https://www.youtube.com/watch?v=iDB2_JROkh8&t=785s