Message-ID:	<347D1100.4800@post.comstar.ru>
Date:	Thu, 27 Nov 1997 09:19:44 +0300
From:	Dim Zegebart <zager AT post DOT comstar DOT ru>
Reply-To:	zager AT post DOT comstar DOT ru
Organization:	Comstar Ltd.
MIME-Version:	1.0
To:	Orlando Andico <orly AT dilnet DOT upd DOT edu DOT ph>
CC:	DJGPP Mail List <djgpp AT delorie DOT com>
Subject:	Re: How to find primes? (Offtopic)
References:	<Pine DOT SGI DOT 3 DOT 96 DOT 971127092321 DOT 28460A-100000 AT gibson DOT eee DOT upd DOT edu DOT ph>

Orlando Andico wrote:
> 
> 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).
It's good method and can be improoved by checking Rabin's number in
usual way -
try to divide on each previous prime number.

-- 
Regards,
Dim Zegebart, 
Moscow Russia.
Ghostly basement : http://www.geocities.com/siliconvalley/pines/7817
DZCOMM - comm library for Allegro

- Raw text -