Double factorial and primorial

bodrato at bodrato at
Fri Dec 23 15:39:41 CET 2011


Il Gio, 22 Dicembre 2011 9:23 pm, Torbjorn Granlund ha scritto:
> nisse at (Niels Möller) writes:
>   Then I imagine it would be good to use Marco's layout, with one bit for
>   each number equal to ±1 (mod 6). (The Erathostenes code I wrote a while
>   ago uses the easier representation of one bit per odd number).

If the same layout is used (bit 0 represents the number 5, bit b the
number (b*3+4)|1, and the number n is represented by bit (n-5|1)/3) and it
is possible to store the full bitmap to cycle on it... I'll be happy to
replace the calls in fac_ui with the new function :-)

To be honest, the layout is not important.

> I can now find all primes < 10^9 in 1.3 s on the Phenom system.

When I wrote my sieve, I used to compute the sum of all primes up-to a
given limit to measure the time required for sieving and looping. As a
side effect, you also obtain a checksum, to avoid trivial mistakes :-)



More information about the gmp-devel mailing list