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. INPUT: Một dòng duy nhất ghi số nguyên dương N ( 0 < N < 10^9 ). OUTPUT: In ra kết quả bài toán. Gởi ý: số có đúng 9 ước có dạng là x^8 (x là số nguyên tố )
vd
inp 
1000

out 

8

giải bằng c++

#include<bits/stdc++.h>
#define ll long long
#define ios ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#pragma GCC optimize("O3","unroll-loops")
#pragma GCC optimize("Ofast")
using namespace std;
vector<int>a;
void sang(int n){
    bool snt[n + 1];
    memset(snt, true, sizeof(snt));
    for (int p = 2; p * p <= n; p++)
    {
        if (snt[p] == true)
        {
            for (int i = p * p; i <= n; i += p)
                snt[i] = false;
        }
    }
    for (int p = 2; p <= n; p++)
        if (snt[p]) a.push_back(p);
}
int main() {
    ios
    ll n;
    cin >> n;
    sang(4e4);
    int k = a.size();
    int d = 0;
    for (int i = 0; i < k; i++) {
        // Xét th những số có dạng x^8
        ll t = pow(a[i], 8);
        if (t <= n && t > 0) d++;
        for (int j = i + 1; j < k; j++) {
            // Xét th nhưng số có dạng (x.y)^2(x,y khác nhau)
            t = pow((ll)(a[i] * a[j]), 2);
            if (t <= n && t > 0) d++;
        }
    }
    cout << d;
    return 0;
}