Re: Simple primality testing

[spiritway]

You might consider generating a list of primes below a given number, and keeping it on disk. Then randomly access one of those numbers. I don't know exactly how many primes are less than 10**8 or so, but it's not altogether overwhelming.

[ambrus]

See the other answer I gave in this thread: Re^2: Simple primality testing.

[Anonymous Monk]

#!/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));

[demerphq]

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. :-)

[hsmyers]

Pub quizzes would probably prefer 'prime' in reference to beef rather than integers.