## Project: Number of Primes

The number of primes equal to or less than a number x is denoted by the function `π(x)`. There is no easy way to compute this function although there are ways to compute a list of primes. Use the SieveOfEratosthenes project to generate a file of prime numbers less than 1,000,000. Then write a function `π(x)` that searches the file for the answer. The function should return the number of primes read before a value greater than x is found. To improve efficiency for subsequent calls to `π(x)` you should only read the file the first time the function is called and store the prime values in an array. This way subsequent calls to `π(x)` don't need to re-read the file. Write a test program to print the values of `π(x)` for x that are powers of 2 up to `2^19`. Will this approach work if you want to compute values for x up to 1,000,000,000 by generating an approprite file of primes? Modify the program to use an estimate `x/(ln x - 1)` for values greater than are found in the primes data file. Test by computing `π(x)` up to `2^30`.

See [[How Many Primes Are There?]]

See SieveOfEratosthenes

## Output

**g++ -std=c++17 NumberOfPrimes.cpp -o NumberOfPrimes -lfmt**$

**./NumberOfPrimes**Reading prime file ../../data/text/primes1M.txt... π(2) = 1 π(4) = 2 π(8) = 4 π(16) = 6 π(32) = 11 π(64) = 18 π(128) = 31 π(256) = 54 π(512) = 97 π(1024) = 172 π(2048) = 309 π(4096) = 564 π(8192) = 1028 π(16384) = 1900 π(32768) = 3512 π(65536) = 6542 π(131072) = 12251 π(262144) = 23000 π(524288) = 43390 π(1048576) = 81519 π(2097152) = 154702 π(4194304) = 294353 π(8388608) = 561397 π(16777216) = 1073019 π(33554432) = 2054938 π(67108864) = 3942518 π(134217728) = 7576513 π(268435456) = 14582447 π(536870912) = 28106558 π(1073741824) = 54244685