A simple sieve in Phobos?

[Dan Killebrew]

On Wednesday, 19 March 2014 at 01:29:16 UTC, bearophile wrote:

> I suggest a Phobos module named "combinatorics" (or just 
> "combs"?). It's not meant to be a complete library of 
> combinatorics algorithms, nor to contain the most optimized 
> algorithms around. It's meant to be a collection of efficient 
> but sufficiently short implementations of the few 
> algorithms/ranges you need most often. Everything else, 
> including the most efficient code, I my opinion should be left 
> to specialized numerical libraries external to Phobos (or could 
> be added later if Phobos gains more developers).
>
> I think the most commonly useful functions are:
>
> - A lazy range (a simple unbounded segmented Sieve) that 
> generates primes numbers very quickly, in a given range, or 
> from 2;
> - A isPrime() function. Probably it should cache some of its 
> computations.
>
> - A function to compute the GCD on ulongs/longs/bigints is 
> useful.
> (Issues 4125 and 7102).
>
> - An efficient and as much as possibly overflow-safe 
> binomial(n,k) that returns a single number.
>
> I'd also like permutations/combinations/pairwise ranges (Phobos 
> already has a permutations, but it's designed on the legacy C++ 
> style of functions, so it's not good enough).
> (See ER issue 6788 for pairwise. A the moment I can't find my 
> Bugzilla ER entry for permutations/combinations, but you can 
> see the good API for the permutations/combinations ranges in 
> the code I have written here: 
> http://rosettacode.org/wiki/Permutations#Fast_Lazy_Version  See 
> also the good API of the Python combinations/permutations here: 
> http://docs.python.org/3/library/itertools.html#itertools.permutations
>  note also the useful "r" and "repeat" arguments).
>
> With such 7 functions/ranges you can do lot of things :-)
>
> Bye,
> bearophile


I've wanted exactly this. I was doing the euler project problems 
and had to implement my own prime sieve, isPrime range, GCD, 
binomial, and combination function (I used Phobos' permutation 
function, but was a bit disappointed that it wasn't implemented 
as a range). Being familiar with the Python 
combinations/permutations functions, I was looking for similar 
functionality in Phobos and was sad to find it missing. So +1 for 
a combinatorics module, and for a numerical/prime module.