prime_sieve [Was: primorial(negative)]

[Marco Bodrato]

Ciao,

Il Gio, 12 Novembre 2015 10:10 am, paul zimmermann ha scritto:
>> Suggestions for the interface?
>
> mpz_prime_t p;

I'm not sure the sieve make sense for mpz sizes... with the current code
we can only implement a fast sieve on unsigned long... I try with an
interface Niels proposed long ago (
https://gmplib.org/list-archives/gmp-devel/2011-December/002124.html )...

unsigned long
gmp_prime_sieve (unsigned long start, unsigned long end,
	         void *ctx, prime_callback_func *f);

(he proposed an mpz_ prefix, but all arguments are unsigned long...)

I attach the code.

On my laptop, timings, compared with primesieve, are:

$ time ~/primesieve-5.6.0/primesieve -t1 -q 1234567891
Primes : 62106579
real	0m0.817s
$ gcc -DMAINPI ps.c -I. .libs/libgmp.a -o pc&&time ./pc 1234567891
pi(0 .. 1234567891)=62106579
real	0m1.573s
$ gcc -O2 -DMAIN ps.c -I. .libs/libgmp.a -o ps&&time ./ps 1234567891
pi(0 .. 1234567891)=62106579
pi(0 .. 1234567891,=3 mod 4)=31054486
real	0m2.814s

The last one is the program implementing the interface above. It is slower
than simply counting primes and much slower than the sieve-centric program
primesieve, but it can be used to eg. count the primes congruous to 3
modulo 4 in the interval :-)

I'm not sure a function not dealing with "big numbers" really belong to
GMP, and surely the attached one is not the "final" implementation (if you
want to scan the interval [1234000 .. 1234500] it blindly sieves starting
from 0). But maybe it can stimulate some other suggestions.

Regards,
m

PS: if linked with the released GMP version, tests can result some 10%
slower.

-- 
http://bodrato.it/