Date: Thu, 27 Nov 1997 09:25:40 +0800 (GMT)
From: Orlando Andico <orly AT dilnet DOT upd DOT edu DOT ph>
To: Peter Palotas <blizzar AT hem1 DOT passagen DOT se>
cc: djgpp AT delorie DOT com
Subject: Re: How to find primes? (Offtopic)
In-Reply-To: <3.0.16.19971026204541.238f1cf6@hem1.passagen.se>
Message-ID: <Pine.SGI.3.96.971127092321.28460A-100000@gibson.eee.upd.edu.ph>
MIME-Version: 1.0
Content-Type: TEXT/PLAIN; charset=US-ASCII
Precedence: bulk

On Sun, 26 Oct 1997, Peter Palotas wrote:

> I was just wondering if anyone knew of a nice fast mehtod of finding prime
> numbers?  ex. finding all 5-number prime numbers, (10000-99999)?
> 
> I know this is off topic, but I don't have newsgroup access, and this is
> the only place I know of where to find programmers.

There is a method known as Rabin's test for primality. It does not
guarantee that the number tested is prime, however, there is a very large
chance that it is so.

Select 100 numbers randomly from 1.. N (where N is the number to be tested
for primality). See if N is factorable by any of the 100 numbers. If not,
then it is prime.

This might sound really stupid, but it actually works (most of the time).
I got the idea from a book, "Out of their minds" which follows the
discoveries of some great computer scientists (Djikstra, Rabin, the fellow
who designed the Connection Machine, et al).
 
-------------------------------------------------------------------
Orlando Alcantara Andico              Email: orly AT dilnet DOT upd DOT edu DOT ph
ICBM:  14 30 00 N  120 59 00 E               POTS:  (+632) 932-2385
"If I shed a tear I won't cage it, I won't fear love, and if I feel
 a rage I won't deny it, I won't fear love."      - Sarah Mclachlan