Re: LF: Prime Number Generator
[Prev][Next][Index][Thread]
Re: LF: Prime Number Generator
On Sun, 22 Dec 1996, Jonathan Oliver wrote:
> I am going to writing a prime number generator for 68k assembly. I have
> written a generator for BASIC, and I'm about to translate it into assembly.
> Does anyone have ANY ideas on how to make this program more efficient.
> (Just make some changes to the code, and send them back to me.) One more
> thing, this generator gets all the prime numbers from 3 and up. It skips
> the number 2 for the sake of speed...
>
>[Snip]
What size of prime numbers are you looking to generate? I know that a
more efficient (speed-wise) algorithm would be the famed "Sieve of
Erastasthenes" (sp?). However, that particular algorithm is incredibly
memory intensive (one bit of memory for each number up to the max). It
does, however have the benefit of being O(sqrt) rather than O(1), that is,
it is much faster for large numbers.
The sieve of erastasthenes goes something like this:
10 defint a-z
20 MAX=5000
30 DIM HoldNum(MAX)
40 for j=2 to sqrt(MAX)
45 if HoldNum(j) then goto 100
50 k=2*j
60 do
70 HoldNum(k)=1
80 k=k+j
90 loop until k>MAX
100 next j
110 for Display=2 to MAX
120 if HoldNum(Display)=0 then print Display
140 next Display
Note, that in an asm program, rather than an array of integers (that is,
two bytes for each number) an array of bits could be implemented (rather
easily..) so as not to waste the 15 bits of memory that this basic program
wastes...
Follow-Ups:
References: