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>
Content-Type: text/plain; charset=us-ascii
Content-Transfer-Encoding: 7bit
Precedence: bulk

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