Pure Programmer

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

Solution