nefu117素数定律

nefu117素数定理

题意：给你一个n，计算1~10^n次方之间有多少个素数，输出该数的位数。

思路：素数定理，小于一个正整数x的素数有多少个，在n越来越大，接近 n / log(n) 计算机用log表示以e为底的对数

所以只要先算出 n / log(n) 在取log 就是位数

n = 10^n

log10( n / log(n) ) = log10(10^n) - log10(log(10^n)) = n - log10(n*log(10)) = n - log10(n) - log10(log(10));

对数运算，相乘等于相加，相除等于想减

#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
using namespace std;

int main()
{
    int n;
    while(scanf("%d",&n) != EOF)
    {
        double m = n - log10(n) -log10(log(10) );
        printf("%d\n",int(m) + 1 );
    }
    return 0;
}