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: