Educational Codeforces Round 12 F.Four Divisorsはxより小さい素数を求める（解決待ち）

F.Four Divisors
テーマ接続:
http://www.codeforces.com/contest/665/problem/F
Description
If an integer a is divisible by another integer b，then b is cared the divisor of a.
For example:12 has positive 6 divisors.They are 1,2,3,4,6 and 12.
Let’s define a function D(n)—number of integers between 1 and n(inclusive)which has exactly four positive divisors.
Between 1 and 10 only the integers 6、8 and 10 has exactly four positive divisors.So、D（10）̵=̵3.
You are given an integer n.You have to calculate D(n)
Input
The only line contains integer n（1̵≦̵n̵≦̵1011）—the parameter from the problem statement.
Output
Print the only integer c-the number of integers between 1 and n with exactly four divisors.
Sample Input
10
Sample Output
3
ベント
題意
nをあげます。nの内に何個の数の因子があるかを聞いてください。ちょうど4個あります。
クイズ:
数は明らかに二つの可能性があります。p、qは素数です。
そしてqqqこれはn^1/3の複雑さの中に出ることができます。
pqなら、小さいのを列挙して、count([n/p]を素早く求めることができればいいです。
このおもちゃは一つの版をかすめ取った。
研究……
コード

#include<bits/stdc++.h>
using namespace std;

#define MAXN 100
#define MAXM 100010
#define MAXP 666666
#define MAX 10000010
#define clr(ar) memset(ar, 0, sizeof(ar))
#define read() freopen("lol.txt", "r", stdin)
#define dbg(x) cout << #x << " = " << x << endl
#define chkbit(ar, i) (((ar[(i) >> 6]) & (1 << (((i) >> 1) & 31))))
#define setbit(ar, i) (((ar[(i) >> 6]) |= (1 << (((i) >> 1) & 31))))
#define isprime(x) (( (x) && ((x)&1) && (!chkbit(ar, (x)))) || ((x) == 2))

using namespace std;

namespace pcf{
    long long dp[MAXN][MAXM];
    unsigned int ar[(MAX >> 6) + 5] = {0};
    int len = 0, primes[MAXP], counter[MAX];

    void Sieve(){
        setbit(ar, 0), setbit(ar, 1);
        for (int i = 3; (i * i) < MAX; i++, i++){
            if (!chkbit(ar, i)){
                int k = i << 1;
                for (int j = (i * i); j < MAX; j += k) setbit(ar, j);
            }
        }

        for (int i = 1; i < MAX; i++){
            counter[i] = counter[i - 1];
            if (isprime(i)) primes[len++] = i, counter[i]++;
        }
    }

    void init(){
        Sieve();
        for (int n = 0; n < MAXN; n++){
            for (int m = 0; m < MAXM; m++){
                if (!n) dp[n][m] = m;
                else dp[n][m] = dp[n - 1][m] - dp[n - 1][m / primes[n - 1]];
            }
        }
    }

    long long phi(long long m, int n){
        if (n == 0) return m;
        if (primes[n - 1] >= m) return 1;
        if (m < MAXM && n < MAXN) return dp[n][m];
        return phi(m, n - 1) - phi(m / primes[n - 1], n - 1);
    }

    long long Lehmer(long long m){
        if (m < MAX) return counter[m];

        long long w, res = 0;
        int i, a, s, c, x, y;
        s = sqrt(0.9 + m), y = c = cbrt(0.9 + m);
        a = counter[y], res = phi(m, a) + a - 1;
        for (i = a; primes[i] <= s; i++) res = res - Lehmer(m / primes[i]) + Lehmer(primes[i]) - 1;
        return res;
    }
}

long long solve(long long n){
    int i, j, k, l;
    long long x, y, res = 0;

    for (i = 0; i < pcf::len; i++){
        x = pcf::primes[i], y = n / x;
        if ((x * x) > n) break;
        res += (pcf::Lehmer(y) - pcf::Lehmer(x));
    }

    for (i = 0; i < pcf::len; i++){
        x = pcf::primes[i];
        if ((x * x * x) > n) break;
        res++;
    }

    return res;
}

int main(){
    pcf::init();
    long long n, res;
    cin>>n;
    printf("%lld
",solve(n));
    return 0;
}