Re: LF: Prime Number Generator


[Prev][Next][Index][Thread]

Re: LF: Prime Number Generator



Shawn Walker wrote:

> 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:
>
> [cut]
> 
> 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...

The problem is that there isn't so much RAM available on the 92. If you want
all primes to one million, you're in trouble.

-- 
Jimmy Mårdell                "I want to stand in the eye of a storm
mailto:mja@algonet.se         I want to get struck by lightning
http://www.algonet.se/~mja    I want our house to be set on fire
IRC: Yarin                    for us to walk without shelter" /Covenant



References: