Hi Bill!

26 Jul 98 17:10, Bill Birrell (2:2504/200{at}fidonet) wrote to Jussi Hamalainen:

 BB>     Have you considered that each number requires only one bit. Either
 BB> it is prime or it is not. It seems to me that even a 386 can address
 BB> that many bits.

But at some point the average number of non primes between primes will grow
larger than the bits/number (int, long, float) and storing the primes as
numbers will consume less space (and maybe time).

... But examining the first million prime numbers showed that there are an
average of 15 numbers between 2 prime numbers and growing _very_ slowly
(logarithmic or such). So a bitfield will consume less memory unless
someone has a real incredible amount of memory. As the number of
bits/number is growing logarithmically, a bitfield may well be the way with
the lowest memory demands at all.

Jussi, you may want to take a look at the sources of PGP. If generating a
1024 bit key means finding a 1024 bit prime it must have a damn smart
algorithm. It can not divide by 2^1023 (10^307) odd numbers, nor can it
divide by all the primes up to 2^512 which may be about 2^512/512=2^503
(10^151) but probably a little less.

 BB> Bill.

Ciao, Bernhard!

PGP key from pgp-public-keys{at}keys.pgp.net, subj: 'get bernhard kuemel'

--- GoldED/2 2.50+