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
$ perl NumberOfPrimes.pl
Unable to parse: Encountered unexpected character '207'
use POSIX qw(floor);
use Utils;
use strict;
use warnings;
our $PRIME_FILE = "../../data/text/primes1M.txt";
our $primes = [];
sub readPrimes {
my ($filename) = @_;
print "Reading prime file ", $filename, "...\n";
my $ifh;
my $isGood = open($ifh, "<", $filename);
if (!$isGood) {
die Error::IOException->new("Problem opening input file!");
}
binmode($ifh, ":utf8");
my $line;
while ($line = <$ifh>) {
chomp($line);
my $p = Utils::stoiWithDefault($line, 0);
if ($p != 0) {
push(@{$primes}, $p);
}
}
close($ifh);
}
sub binarySearch {
my ($list, $value) = @_;
if ($value < $primes->[0]) {
return -1;
}
if ($value > $primes->[-1]) {
return scalar(@{$primes});
}
my $left = 0;
my $right = scalar(@{$list}) - 1;
while ($left <= $right) {
my $m = int(($left + $right) / 2);
if ($list->[$m] < $value) {
$left = $m + 1;
} elsif ($list->[$m] > $value) {
$right = $m - 1;
} else {
return $m + 1;
}
}
return $left;
}
sub π {
my ($x) = @_;
my $pos = scalar(@{$primes});
if ($pos != 0) {
$pos = binarySearch($primes, $x);
}
if ($pos == scalar(@{$primes})) {
return floor($x / (log($x) - 1) + 0.5);
} else {
return $pos;
}
}
MAIN:
{
binmode(STDOUT, ":utf8");
binmode(STDERR, ":utf8");
binmode(STDIN, ":utf8");
try {
readPrimes($PRIME_FILE);
my $x = 1;
for (my $i = 1; $i <= 30; ++$i) {
$x *= 2;
print Utils::messageFormat("π(\{0:d\}) = \{1:d\}", $x, π($x)), "\n";
}
} catch (Error::Simple $ex) {
print "Error reading input file!\n";
}
}
Solution
Pure Programmer
