Implementing a pi(n) sieve in gmp.

[Allan Menezes]

Dear All,
 One can implement a sieve that calculates pi(n) and the n'th prime Pn and
instant primality check
for small bit strings p[] as follows:
Calculate and implement the following  primes and composites bit string p[]
upto a convenient large n starrting from 2 as such storing the m'th bit as
a 1 if m is prime and 0 otherwise.
Store this string upto n bits as a mpz_t ropp.
Now for all numbers below n primality of m <=n is determine the return
value of mpz_tstbit(mpz_t ropp, m);
For pi(x) x<=n; pi(x)=mpz_popcount(mpz_t ropp,x);
To determine Pm we need more complexity
Pm ~ m ln(m)+/-Delta;
Determine x=m ln(m) - epsilon for a small integer values of epsilon, Delta.
Iterate k=mpz_scan1(mpz_t ropp,x + eps1)
till we get m for the return value m of mpz_popcount(mpz_t ropp,x+esp0);
This can be implemented in many ways but creating built in functions in GMP
and implementing
the last iterative method as a binary search to find m from mln(m)-Delta
would be good.
Thank you,
Thanks for a very fast and excellent Multiple precision library GMP.
We are all in debt to you over the years.
Best wishes,
Allan Menezes
PS It would be nice if mpz_popcount and mpz_scan1 and mpz_scan0 were
implemented to return
as a var to the functions in mpz_t for large p[] bit strings.
It would be nice all bit fiddling mpz instructions returned their values as
mpz_t except for those
functions that return bit values or always small integer values.