NEFU 117-素数个数的位数(素数定理)

题目地址：NEFU 117

题意：给你一个整数N(N<1e9)。假设小于10^N的整数中素数的个数为π(N)。求π(N)的位数是多少。

思路：题目的数据量非常大，直接求肯定TLE，所以考虑素数定理。

素数定理：记π(N)是<=N的素数个数，那么有

一个数x的位数能够用lg(x)+1来求，所以本题中lg(N/InN)+1就是所求，由于N=10^N。所以位数=lg(10^N)-lg(In(10^N))+1=N-lgN-lg(In(10))+1.

#include <stdio.h>

#include <math.h>

#include <string.h>

#include <stdlib.h>

#include <iostream>

#include <sstream>

#include <algorithm>

#include <set>

#include <queue>

#include <stack>

#include <map>

#include <bitset>

#pragma comment(linker, "/STACK:102400000,102400000")

using namespace std;

typedef long long  LL;

const int inf=0x3f3f3f3f;

const double pi= acos(-1.0);

const double esp=1e-7;

const int Maxn=1e6+10;

int main()

{

    double n,m;

    while(~scanf("%lf",&n)) {

        m=(n-log10(n)-log10(log(10)));

        printf("%d\n",(int)m+1);

    }

    return 0;

}