# Prime Numbers up to a million

https://www.emogic.com/cgi/primes/primes.cgi

A Javascript version: Prime Number Generator in Javascript

Generates prime numbers from 2 to 1,000,000 using Eratosthenes’ prime number sieve. Why? Why not.

PERL source code is available:

#!/usr/bin/perl

#Generates prime numbers from 2 to 1,000,000 using Eratosthenes’ prime number sieve. Why? Why not.

#prints out NPH allowing the script to output as it generates and prevents 30 sec timeout
use CGI qw(:standard -nph);
print “Content-type: text/plain\n\n”;
\$| = 1;

print “Prime Number Generator\n”;

\$tt = time();

\$limit = 1000000 ;
\$limitSqrt = int(sqrt(\$limit));

print “Prime Numbers up to \$limit\n\n”;

# \$notprime{\$num} = undef \$num is prime
# \$notprime{\$num} = 1 \$num is not prime

#calculate and print primes up to sqrt(\$limit)
#we are actually generating a list of non primes by adding each number (up to sqrt(\$limit) ) repeatedly until we reach \$limit.
#all sums will not be prime
for(\$num=2; \$num <= \$limitSqrt; ++\$num)
#for(\$num=2; \$num <= \$limit; ++\$num)
{

\$sum = \$num;

if (\$notprime{\$num})
{ #this number is not a prime so it’s factors’s multiples have already been checked off
next;
}
else
{ #this number has not yet been marked ‘not prime’ so it must be prime as we have already checked for all possible lesser factors
print “\$num\n”
}
while (\$sum < \$limit) #add \$num repeatedly up to limit. all sums will not be prime. same as all multiples of \$num
{
\$sum = \$sum + \$num;
\$notprime{\$sum} = 1; #not prime
}
}

#all non primes have been found up to \$limit at this point.

#print already calculated primes after sqrt(\$limit)
for(\$num=\$limitSqrt + 1; \$num < \$limit; ++\$num)
{
if (!\$notprime{\$num})
{
print “\$num\n”
}
}

print “\n\nSeconds: ” ;
print time() – \$tt;
print “\n\n” ;

1;