use 5.010;
use strict;

use Carp qw/croak/;
use Time::HiRes qw/time/;

sub isPrime1 (_)
{
	my $num = shift;

	return if $num == 1;  # 1 is not prime

	croak "usage: isPrime(NATURAL NUMBER)"
		unless $num =~ /^[1-9][0-9]*$/;

	for my $div (2 .. sqrt $num)
	{
		return if $num % $div == 0;
	}
	return 1;
}

sub isPrime2
{
	my $toTest    = shift;
	my $sqrtLimit = sqrt $toTest;

	my $sieve = q{};
	vec( $sieve, 0      , 1 ) = 1;
	vec( $sieve, 1      , 1 ) = 1;
	vec( $sieve, $toTest, 1 ) = 0;

	my $marker = 1;
	while ( $marker < $sqrtLimit )
	{
		my $possPrime = $marker + 1;
		$possPrime ++ while vec( $sieve, $possPrime, 1 );

		my $fill = 2 * $possPrime;
		while ( $fill <= $toTest )
		{
			vec( $sieve, $fill, 1 ) = 1;
			$fill += $possPrime;
		}
		last if vec( $sieve, $toTest, 1 );

		$marker = $possPrime;
	}

	return not vec($sieve, $toTest, 1);
}

say q[  NUMBER : TOBYINK       JOHNGG        ];
say q[  NUMBER : RESULT  TIME  RESULT  TIME  ];

for my $num (qw(75 169 229 367 369 8794 9227 10807 11939 14803 19937 19938 39783 47083 199933))
{
	printf('%8d : ', $num);
	timeit($num, $_) for \&isPrime1, \&isPrime2;
	print "\n";
}

sub timeit
{
	my ($n, $f) = @_;
	my $start = time();
	print($f->($n) ? "YES " : "NO  ");
	my $end = time();
	printf '%.06f  ', ($end - $start);
}