Yêu cầu Cho một số nguyên dương N, hãy viết chương trình đếm số lượng số có đúng 9 ước và không lớn hơn N. Dữ liệu Một dòng duy nhất ghi số nguyên dương N (0<N<10^9 ). Kết quả In ra kết quả bài toán. Ví dụ INPUT 1000 OUTPUT 8

`+` Ý tưởng

`@` Một số có đúng `9` ước là số có dạng `(xy)^2` (với `x` và `y` là hai số nguyên tố khác nhau) hoặc `x^8` (với `x` là một số nguyên tố)

`+` Code (Limit: `n \leq 10^9`)

#include <bits/stdc++.h>
#define ll unsigned long long
using namespace std;
vector<int> primes;
void SieveOfEratosthenes(int n){
    bool prime[n + 1];
    memset(prime, true, sizeof(prime));
    for (int p = 2; p * p <= n; p++) {
        if (prime[p] == true) {
            for (int i = p * p; i <= n; i += p) prime[i] = false;
        }
    }
    for (int p = 2; p <= n; p++)
        if (prime[p]) primes.push_back(p);
}
int main(){
    int n;
    cin >> n;
    SieveOfEratosthenes(50001);
    int ans = 0;
    int pl = primes.size();
    for (int i = 0; i < pl; i++){
        ll tmp = pow(primes[i], 8);
        if (tmp <= n and tmp > 0) ans++;
        for (int j = i + 1; j < pl; j++){
            ll tmp = pow((primes[i]*primes[j]),2);
            if (tmp <= n and tmp > 0) ans++;
        }
    }
    cout << ans;
    return 0;
}