Nefu117 number of prime numbers [prime number theorem]

Topic linking ：

​ ​http://acm.nefu.edu.cn/JudgeOnline/problemshow.php?problem_id=117​​

The main idea of the topic ：

Give you an integer N(1 < N < 1000000000), If it is less than 10^N The number of primes in the integer of is π(N),

So here comes the question ： seek π(N) What are the digits of .

Ideas ：

The number of primes π(N) There is a prime theorem ：π(N) = N/ln(N). In this question π(10^N) = 10^N/ln(10^N).

The problem is transformed into ： seek N^10*ln(N^10) How many people are there . Co ownership x position , Available 10^x = 10^N/ln(10^N).

Take logarithms on both sides at the same time log10, have to ：

             10^x = N^10 / ln(N^10)

 log10(10^x) = log10( 10^N / ln(10^N) )

                    x = N - log10( ln(10^N) )

                    x = N - ( log10(N) + log10( ln10 )

                    x = N - log10(N) - log10( ln10 )

Last x integer +1, Get the corresponding digits .

Prime number theorem ：

Positive real numbers x, Definition π(x) Is not greater than x The prime number of . When x Approach ∞,π(x) and x/ln x Ratio approach of 1.

AC Code ：

Log in and copy

      
      

       
       #include<iostream>
       
       

       
       #include<algorithm>
       
       

       
       #include<cmath>
       
       

       
       using 
       
       namespace 
       
       std;
       
       

       
       const 
       
       double 
       
       e 
       
       = 
       
       2.71828;
       
       

       
       

       
       int 
       
       main()
       
       
{
       
       
    
       
       int 
       
       N;
       
       
    
       
       while(
       
       cin 
       
       >> 
       
       N)
       
       
    {
       
       
        
       
       double 
       
       M 
       
       = 
       
       double(
       
       N) 
       
       - 
       
       log10(
       
       N) 
       
       - 
       
       log10(
       
       log(
       
       10));
       
       
        
       
       cout 
       
       << (
       
       int)
       
       M 
       
       + 
       
       1 
       
       << 
       
       endl;
       
       
    }
       
       

       
       
    
       
       return 
       
       0;
       
       
}
      
      
      
      

       
       
1.
       
       
2.
       
       
3.
       
       
4.
       
       
5.
       
       
6.
       
       
7.
       
       
8.
       
       
9.
       
       
10.
       
       
11.
       
       
12.
       
       
13.
       
       
14.
       
       
15.
       
       
16.
       
       
17.