Three technical remarks about GMP functions

Alexander Kruppa alexander.kruppa at
Wed Jun 8 14:48:39 CEST 2005

Sisyphus wrote:
> ----- Original Message ----- 
> From: "NUNES" <raulnunes at>
>>1st - I've created a base of primes going from 2 thru 2^32-5 (that is,
> primes that can be stored in 32-bits words).
> Haven't fully looked at what you're doing, but you may well find that it's
> more efficient to generate the primes on the fly and read them from memory,
> rather than read them from disk. See (eg)
> .
> Cheers,
> Rob

Or if you want a list of primes in memory and only access them 
sequentially, store the differences between consecutive primes. Except 
between 2 and 3, this difference is even, so you may store (p_{i+1} - 
p_i)/2. The largest gap between primes <2^32 is  336 following 
3842611109, so by storing the difference / 2 you can keep everything in 
a table by bytes. The gaps between consecutive primes < N seems to not 
exceed (ln N)^2. The first gap you couldn't store in a byte this way is 
of length 514, following 304599508537.


More information about the gmp-discuss mailing list