[BOJ/Gold 5] 백준 1456 거의 소수(C++)

문제 링크

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

1456번: 거의 소수

 

문제

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

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

입력

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

출력

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

제한

• 1 ≤ A ≤ B ≤ 10^14

예제 입력 1

1 1000

예제 출력 1

25

예제 입력 2

1 10

예제 출력 2

3

예제 입력 3

5324 894739

예제 출력 3

183

알고리즘 분류

• 소수 판정

풀이

에라토스테네스의 체를 통해 소수와 소수가 아닌 수를 구분하여 기록한다.

DP[i] = i이면 i는 소수다.

이제 A, B의 N제곱근을 각각 구하고 그 사이에 있는 소수들의 N제곱수가 A 이상 B 이하인지 확인하고 범위 안에 있다면 거의 소수로 판정한다.

이것을 A, B의 N제곱근이 1이 될 때까지 N을 1씩 증가시키면서 반복한다.

마지막으로 거의 소수의 개수를 출력한다.

코드

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

using namespace std;
LL DP[MAX];
LL A, B;
set<LL> S;

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

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

void settings() {
    LL R = 2;
    while (1) {
        LL NewA = (LL)floor(pow((double)A, 1.0 / (double)R));
        LL NewB = (LL)floor(pow((double)B, 1.0 / (double)R));
        for (LL i = NewA; i <= (NewB + 1); i++) {
            if (DP[i] == i) {
                LL Now = (LL)pow((double)i, (double)R);
                if ((Now >= A) && (Now <= B)) {
                    S.insert(Now);
                }
            }
        }
        if ((NewA == 1) && (NewB == 1)) {
            break;
        }
        else {
            R++;
        }
    };
}

void find_Answer() {
    cout << (LL)S.size() << "\n";
}

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

    return 0;
}