paul zimmermann Paul.Zimmermann at
Fri Nov 13 13:56:53 UTC 2015

> I haven't followed this discussion in detail, but perhaps
> gmp/nextprime.c (i.e., nextprime.c at the top-level) is a good start?
> This sieve uses a tiny sieving table (512 bytes) and thus will behave
> unusually poorly when sieving for primes p where sqrt(p) >> 512.  That
> is fixable, e.g., by keeping offsets in a binary minheap.

you can also consider the file utils/getprime.c from CADO-NFS:

zimmerma at tarte:~/svn/cado-nfs/utils$ gcc -O3 -g -DMAIN getprime.c
zimmerma at tarte:~/svn/cado-nfs/utils$ time ./a.out 1000000000

real    0m2.572s
user    0m2.268s
sys     0m0.000s

This is almost 1000 times faster than GMP.


More information about the gmp-discuss mailing list