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 called 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

Hint

题意

给你n，问你n以内有多少个数的因子数恰好有4个

题解：

数显然就两种可能pq或者qqq，其中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\n",solve(n));
return 0;
}