Re^2: Simple primality testing

#!/usr/bin/perl -w

# a not too bad approximation to the number of primes 
# less than N is approximately N/log(N).  Better methods 
# exist, but none are as simple...

my $n1 = 10**8;
my $n2 = 2**32;

$\="\n";

# ~ 5428681 
print "Number of primes less than $n1 is ",int($n1/log($n1));

# ~ 193635250
print "Number of primes less than $n2 is ",int($n2/log($n2));
[download]

Comment on Re^2: Simple primality testing Download Code

Replies are listed 'Best First'.
Re^3: Simple primality testing by demerphq (Chancellor) on Nov 24, 2005 at 08:01 UTC
Actually since these are signed longs it only goes up to 2^31-1, which is a prime, a Mersenne Prime actually. (For those that missed this bit, a Mersenne prime is any prime expressable in the form 2^N-1.) I dont know if I'm the only one that finds it interesting that the highest number you can represent with a long is a prime, but I do. :-) Now if only they would use questions like this on pub-quizzes. :-) --- $world=~s/war/peace/g	[reply]
Re^4: Simple primality testing by hsmyers (Canon) on Nov 26, 2005 at 15:39 UTC
Pub quizzes would probably prefer 'prime' in reference to beef rather than integers. --hsm "Never try to teach a pig to sing...it wastes your time and it annoys the pig."	[reply]