primorial(negative)
paul zimmermann
Paul.Zimmermann at inria.fr
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
pi(1000000000)=50847534
real 0m2.572s
user 0m2.268s
sys 0m0.000s
This is almost 1000 times faster than GMP.
Paul
More information about the gmp-discuss
mailing list