loj #6235. 区间素数个数

#6235. 区间素数个数

题目描述

求 1∼n 1sim n1∼n 之间素数个数。

输入格式

一行一个数 n nn 。

输出格式

一行一个数，表示答案。

样例

样例输入

10

样例输出

4

样例解释 1

2,3,5,72,3,5,72,3,5,7

数据范围与提示

对于 100% 100\%100% 的数据，2≤n≤1011 2 leq n leq 10^{11}2≤n≤10​11​​。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#define maxn 316228
using namespace std;
long long n;
bool vis[maxn];
int lim,p[27294],sum[maxn],last[maxn*2],cnt;
long long val[maxn*2],f[maxn*2];
void prepare(){
    for(int i=2;i<=lim;i++){
        if(!vis[i])p[++p[0]]=i;
        sum[i]=sum[i-1]+!vis[i];
        for(int j=1;j<=p[0]&&i*p[j]<=lim;j++){
            vis[i*p[j]]=1;
            if(i%p[j]==0)break;
        }
    }
}
int main(){
    cin>>n;lim=sqrt(n);
    prepare();
    for(long long i=1;i<=n;i=n/(n/i)+1)
        val[++cnt]=n/i;
    reverse(val+1,val+cnt+1);
    copy(val+1,val+cnt+1,f+1);
    for(int i=1;i<=p[0];i++){
        for(int j=cnt;j>=1;j--){
            long long k=val[j]/p[i];
            long long pos=k<=lim?k:cnt+1-n/k;
            if(k<p[i])break;
            f[j]-=f[pos]+last[pos]-i+1;
            last[j]=i;
        }
    }
    printf("%lld",sum[lim]+f[cnt]-1);
    return 0;
}