Quote: Tycho might not like this, but there's an entry in IO.IN's wiki about GenPrime.
http://www.ferrousmoon.com/wiki/index.php/GenPrime
Here are the current versions (Ruby, C, and PHP listed here only, for now):
CCode: /*
* GenPrime
*
* (c) 2006-2008 Steven Noonan.
* Licensed under the New BSD License.
*
*/
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <memory.h>
#include <sys/time.h>
int
isPrime ( unsigned long _candidate )
{
unsigned long i, limit;
/* 0 and 1 aren't prime. */
if ( _candidate < 2 ) return 0;
/* All numbers less than 4 are prime, except '1' */
if ( _candidate < 4 ) return -1;
/* Other than 2, even numbers are not prime */
if ( _candidate % 2 == 0 ) return 0;
/* All primes are of the form 6k+i (where i = -1 or 1), except for 2 or 3. */
if ( ( _candidate + 1 ) % 6 != 0
&& ( _candidate - 1 ) % 6 != 0 )
return 0;
/*
if n is composite then it can be factored into two values,
at least one of which is less than or equal to sqrt(n)
*/
limit = (unsigned long)sqrt ((double)_candidate);
/* Now test all other odd numbers up to sqrt(n) */
for ( i = 3; i <= limit; i += 2 ) if ( _candidate % i == 0 ) return 0;
return 1;
}
unsigned long
genPrime ( unsigned long _maxToFind )
{
unsigned long count = 0, num;
for ( num = 1; count < _maxToFind; num++ )
{
if ( isPrime ( num ) )
{
count++;
}
}
/* Returning 'count' prevents the compiler from optimizing this function out as worthless */
return count;
}
int main ( int argc, char **argv )
{
struct timeval start;
struct timeval finish;
unsigned long i;
for ( i = 100000; i <= 500000; i += 100000 )
{
gettimeofday ( &start, NULL );
genPrime ( i );
gettimeofday ( &finish, NULL );
double secondsElapsed = (double)( finish.tv_sec - start.tv_sec ) +
( (double)finish.tv_usec - (double)start.tv_usec ) / 1000000.0;
printf ( "Time for %9lu primes: %6.3lf seconds (%lu PPS)\n", i, secondsElapsed,
(unsigned long)((double)i / secondsElapsed) );
}
return 0;
}
RubyCode: #!/usr/bin/ruby -w
#
# GenPrime
#
# (c) 2006-2008 Steven Noonan.
# Licensed under the New BSD License.
#
#
def
isPrime ( _candidate )
# 0 and 1 aren't prime.
if _candidate < 2
return 0
end
# All numbers less than 4 are prime, except '1'
if _candidate < 4
return -1
end
# Other than 2, even numbers are not prime
if _candidate % 2 == 0
return 0
end
# All primes are of the form 6k+i (where i = -1 or 1), except for 2 or 3.
if ( _candidate + 1 ) % 6 != 0 and ( _candidate - 1 ) % 6 != 0
return 0
end
# if n is composite then it can be factored into two values,
# at least one of which is less than or equal to sqrt(n)
limit = Math.sqrt( _candidate )
# Now test all other odd numbers up to sqrt(n)
i = 3
while i <= limit
if ( _candidate % i == 0 )
return 0
end
i += 2
end
return 1
end
def
genPrime ( _maxToFind )
num = 1
count = 0
while count < _maxToFind
if isPrime( num )
count += 1
end
num += 1
end
# Returning 'count' prevents the compiler from optimizing this function out as worthless
return count
end
i = 100000
while i <= 500000
start = Time.now
genPrime( i )
finish = Time.now
secondsElapsed = finish.to_f - start.to_f
printf( "Time for %9u primes: %6.3f seconds (%u PPS)\n", i, secondsElapsed, i / secondsElapsed );
i += 100000
end
PHPCode: <?php
/*
* GenPrime
*
* (c) 2006-2008 Steven Noonan.
* Licensed under the New BSD License.
*
*/
function
isPrime ( $_candidate )
{
/* 0 and 1 aren't prime. */
if ( $_candidate < 2 ) return 0;
/* All numbers less than 4 are prime, except '1' */
if ( $_candidate < 4 ) return -1;
/* Other than 2, even numbers are not prime */
if ( $_candidate % 2 == 0 ) return 0;
/* All primes are of the form 6k+i (where i = -1 or 1), except for 2 or 3. */
if ( ( $_candidate + 1 ) % 6 != 0
&& ( $_candidate - 1 ) % 6 != 0 )
return 0;
/*
if n is composite then it can be factored into two values,
at least one of which is less than or equal to sqrt(n)
*/
$limit = sqrt ( $_candidate );
/* Now test all other odd numbers up to sqrt(n) */
for ( $i = 3; $i <= $limit; $i += 2 ) if ( $_candidate % $i == 0 ) return 0;
return 1;
}
function
genPrime ( $_maxToFind )
{
$count = 0;
for ( $num = 1; $count < $_maxToFind; $num++ )
{
if ( isPrime ( $num ) )
{
$count++;
}
}
return $count;
}
for ( $i = 100000; $i <= 500000; $i += 100000 )
{
$start = microtime(true);
genPrime ( $i );
$finish = microtime(true);
$secondsElapsed = $finish - $start;
printf ( "Time for %9lu primes: %6.3lf seconds (%lu PPS)\n", $i, $secondsElapsed, $i / $secondsElapsed );
}
?>
|
..thats a start atleast, eh?