http://www.perlmonks.org?node_id=1137385


in reply to Re: Unable to Understand grep and hash use for prime no.
in thread Unable to Understand grep and hash use for prime no.

(2) hash access slows disproportionately whereas this lookup could just be an array. That array could be packed down to one bit per element for the most efficient storage, given that it has only boolean values. Lookup (and registration) can be achieved without unpacking from that using bit operators such as '<<' and '&', thereby winning on processing as well as storage.

What you describe is a primes sieve. One common prime generation technique is the Sieve of Eratosthenes. Another (sometimes slightly faster, but always more complicated) is the Sieve of Atkin.

I believe danaj has a blazing fast segmented sieve in Math::Prime::Util, and I have a pretty basic non-segmented Sieve of Eratosthenes implementation in Math::Prime::FastSieve.


Dave

  • Comment on Re^2: Unable to Understand grep and hash use for prime no.

Replies are listed 'Best First'.
Re^3: Unable to Understand grep and hash use for prime no.
by anonymized user 468275 (Curate) on Aug 04, 2015 at 18:26 UTC
    Yes that's right, Dave. Coincidentally the sieve technique came up here only three weeks ago when a poster was trying to check a conjecture about Recaman's sequence. In thinking about primes, I did consider XS and C++ funnily enough, until I realised that prime or not is conceptually boolean and can be packed down to bits, so XS and C++ might be less urgent. Nevertheless I totally applaud the work you've done and XS and C++ is a very good choice.

    One world, one people