NetNews Usenet Archive 1992 #19/NN_1992_19.iso/spool/alt/hackers/1335

Text File | 1992-08-30 | 1.6 KB | 36 lines

Newsgroups: alt.hackers
Path: sparky!uunet!zaphod.mps.ohio-state.edu!rpi!cleggp
From: [e-mail] (Paul Jason Clegg)
Subject: Prime Number Generator
Message-ID: <[e-mail]>
Nntp-Posting-Host: aix.rpi.edu
Organization: Rensselaer Polytechnic Institute, Troy, NY
Date: Mon, 31 Aug 1992 01:43:58 GMT
Approved:  [e-mail]
Lines: 24

I'm interested in generating large prime numbers for use in some public key
code encryption schemes, and I'm looking for the fastest way to generate all
the primes from 2 up to as high as I can go on my 386/25 (Using BC++ 3.1, I
figured this is somewhere in the what, 4 billion range?)  Anyway, the first
method I was using was to just try every other (ie. odd) number from 3 to the
integer of the square root of the number being tested for prime-ness.  But
this takes quite a while.  Then in a discrete math class I found some Greek
dude's theorem about just using 2, 3, 5, and 7, and if the number isn't
divisible by any of those four numbers, it's prime.  But I got to thinking,
121 fits that description, but it's the square of 11, so something's amiss
here.  My new algorithm (as soon as I get the HD space for BC++ 3.1) is
going to keep a stack of prime numbers as it finds them; though it'll only
use those prime numbers up until it maxes out their usefullness (ie. reaches
the square of the highest prime number being used) at which point it will
extend the list to the next prime number.  I figure this should be a pretty
good algorithm.

But.  Does anyone know of even more efficient algorithm for determining the
primeness of numbers?  Has anyone ever come up with a O(n) algorithm for it?

...Paul