LibreOJ 6235 区间素数个数

发表于 | 分类于 |

阉割 Min_25 筛大法好。

Min_25 筛算法中有一个过程就是求 \(f\) 在质数处的值。
那么如果我们构造 \(f(n) = 1\) 那这个就相当于求质数的个数了。

代码： 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#include <cstdio>
#include <cmath>
using namespace std;
const long long N = 1e11;
const int MX = 32e4;
long long n;
int lim;
int vis[MX + 5],cnt,prime[MX + 5];
long long lis[2 * MX + 5];
int tot,le[MX + 5],ge[MX + 5];
long long G[2 * MX + 5];
inline int &id(long long x)
{
    return x <= lim ? le[x] : ge[n / x];
}
int main()
{
    for(register int i = 2;i <= MX;++i)
    {
        if(!vis[i])
            prime[++cnt] = i;
        for(register int j = 1;j <= cnt && i * prime[j] <= MX;++j)
        {
            vis[i * prime[j]] = 1;
            if(!(i % prime[j]))
                break;
        }
    }
    scanf("%lld",&n),lim = sqrt(n);
    for(register long long l = 1,r;l <= n;l = r + 1)
    {
        r = n / (n / l);
        lis[id(n / l) = ++tot] = n / l;
        G[tot] = n / l - 1;
    }
    for(register int k = 1;k <= cnt;++k)
    {
        int p = prime[k];
        long long s = (long long)prime[k] * prime[k];
        for(register int i = 1;lis[i] >= s;++i)
            G[i] -= G[id(lis[i] / p)] - (k - 1);
    }
    printf("%lld\n",G[1]);
}