A-第N个质数

求第n个质数
(n<= 1e9)

首先在(0～1e7)范围内的质数我们可以直接欧拉筛解决
但是第(1e9)个的质数是(2e10)级别的

我们考虑二分答案
然后我们要实现的操作就是求(1~n)之间有多少质数，然后二分。

接着我们想一想，一个质数(x),它的判定就是不能被(2 - sqrt(x))之间任何一个数整除，这等价于不能被(2 - sqrt(x))之间任何一个质数整除
同时我们之前预处理的欧拉筛恰好已经帮我们找出了这些质数

于是乎开始DP

(g[i][j])表示前(i)个数中，不能被前(j)个质数整除的数的数量
递推：(g[i][j] = g[i][j - 1] - g[i / p[j]][j - 1])

考虑优化：

1. (j = 0)，(return i)
2. (i leq N), N 是预处理的上界，我们记录(f[i])表示(1~i)之间的质数个数，
   (f[i] leq j) , (return 1)
   (f[sqrt(i)] leq j), (return f[i] - j + 1), 表示(1~i)之间的每一个合数都能被整除，只剩下所有质数和1， 然后我们减去前(j)个质数

以上

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

const int N = 8000000;

int prime[N/10],cnt;
int p[N + 5];
int f[N + 5];

#define int long long

int n;

int g(int x,int y){
    if(x <= 1) return x;
    if(y == 0) return x;
    if(y == 1) return x - x/2;
    if(x <= prime[y]) return 1;
    if(x <= N){
        if(f[x] <= y) return 1;
        if(f[(int)(sqrt(x))] <= y) return f[x] - y + 1;
    }
    return g(x,y - 1) - g(x/prime[y],y - 1);
}

int check(int d){
    int q = sqrt(d);
    return f[q] + g(d,f[q]) - 1;
}

signed main(){
    p[0] = p[1] = 1; f[0] = f[1] = 0;
    for(int i = 2; i <= N; ++ i){
        f[i] = f[i - 1];
        if(!p[i]) prime[++ cnt] = i, ++ f[i];
        for(int j = 1; prime[j] * i <= N; ++ j){
            p[prime[j] * i] = 1;
            if(i % prime[j] == 0) break;
        }
    }
    
    
    scanf("%lld",&n);
    if(n <= cnt) { printf("%d
",prime[n]); return 0; }
    
    int l = N + 1, r = 23000000000ll, ans = -1;
    while(l <= r){
        int mid = (l + r) >> 1;
        int s = check(mid);
        //printf("%lld %lld
",mid,s);
        if(s >= n) { ans = mid; r = mid - 1; }
        else l = mid + 1; 
    }
    printf("%lld
",ans);
    return 0;
}