题目传送门：

Problem : 117

Time Limit : 1000ms

Memory Limit : 65536K

description

小明是一个聪明的孩子，对数论有着很浓烈的兴趣。

他发现求1到正整数10ⁿ 之间有多少个素数是一个很难的问题，该问题的难以决定于n 值的大小。

现在的问题是，告诉你n的值，让你帮助小明计算小于10ⁿ的素数的个数值共有多少位？

input

输入数据有若干组，每组数据包含1个整数n（1 < n < 1000000000），若遇到EOF则处理结束。

output

对应每组数据，将小于10ⁿ 的素数的个数值的位数在一行内输出，格式见样本输出。同组数据的输出，其每个尾数之间空一格，行末没有空格。

sample_input

37

sample_output

36

hint

素数定理

素数定理：素数有无穷多个，能估计出小于一个正实数x的素数有多少个，并用PI(x)来表示，这就是素数定理。随着x的增长，PI(x)/(x/ln(x)) == 1.

这道题的数据量很大，因为10的n次方很大，会溢出，不能直接运算，该题只是求素数分布值的位数。考虑到使用素数定理，因为n/ln(n)与素数分布值PI(n)随着n值的增大越来越接近，值的位数更不会出现误差，所以直接求n/ln(n)的位数即可。

位数公式得知：[log10(n/ln(n))]+1

#include 
    
     #include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          using namespace std;char a[100];int main() { int n; while (cin >> n) { int res = (int) (n - log10(n) - log10(log(10))); //memset(a, 0, sizeof(a)); cout << res + 1<< endl; } return 0;}