[1456] 거의 소수 (C++)

#include <iostream>
#include <vector>

using namespace std;
typedef long long ll;
const int MAX = 10000001;
bool isPrime[MAX];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    ll N, M; cin >> N >> M;

    vector<int> Prime;

    for (int i = 2; i < MAX; i++) {
        if (!isPrime[i]) {
            Prime.push_back(i);
            for (int j = 2 * i; j < MAX; j += i) {
                isPrime[j] = true;
            }
        }
    }

    ll ans = 0LL;

    for (auto x : Prime) {
        ll y = 1LL * x;
        ll tmp = y;
        while (tmp <= M / y) {
            tmp *= y;
            if (tmp >= N) ans++;
        }
    }

    cout << ans;

    return 0;
}

 

1. 수의 범위가 1 <= N <= M <= 10^14

2. 어떤 수가 소수의 N제곱(N>=2)이므로, 10^7까지의 소수를 모두 판별하여 저장한다

=> long long 타입을 사용

3. 소수 벡터 Prime를 사용, tmp * y <= M인 경우에만 판별한다