<div dir="ltr"><div><div>>>      if (p ^^ 2 > b)<br>>>            si = si.max(p ^^ 2 - b);<br><br></div>Can't that be written as:<br><br></div>auto t = p ^^ 2 - b;<br>if (t > 0 && t > si) si = t;<br>

<br></div><div class="gmail_extra"><br clear="all"><div>--<br>Ziad</div>
<br><br><div class="gmail_quote">On Tue, Mar 18, 2014 at 7:23 AM, bearophile <span dir="ltr"><<a href="mailto:bearophileHUGS@lycos.com" target="_blank">bearophileHUGS@lycos.com</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">

There is a efficient Sieve implementation in C++ here:<br>
<br>
<a href="http://code.activestate.com/recipes/577966-even-faster-prime-generator/?in=lang-cpp" target="_blank">http://code.activestate.com/<u></u>recipes/577966-even-faster-<u></u>prime-generator/?in=lang-cpp</a><br>
<br>
There are of course far faster implementations, but its performance is not bad, while being still simple and quite short.<br>
<br>
A D implementation (it's not a final version because the global enums should be removed and replaced with run-time variables or template arguments. And something different from just counting must be added):<br>
<br>
<br>
import std.stdio, std.algorithm, std.typecons;<br>
<br>
enum uint MAX_N = 1_000_000_000U;<br>
enum uint RT_MAX_N = 32_000; // square of max prime under this limit should exceed MAX_N.<br>
enum uint B_SIZE = 20_000;   // not sure what optimal value for this is;<br>
                             // currently must avoid overflow when squared.<br>
<br>
// mod 30, (odd) primes have remainders 1,7,11,13,17,19,23,29.<br>
// e.g. start with mark[B_SIZE/30]<br>
// and offset[] = {1, 7, 11, ...}<br>
// then mark[i] corresponds to 30 * (i / 8) + b - 1 + offset[i % 8].<br>
Tuple!(uint, size_t, uint) calcPrimes() pure nothrow {<br>
    // Assumes p, b odd and p * p won't overflow.<br>
    static void crossOut(in uint p, in uint b, bool[] mark)<br>
    pure nothrow {<br>
        uint si = (p - (b % p)) % p;<br>
        if (si & 1)<br>
            si += p;<br>
        if (p ^^ 2 > b)<br>
            si = si.max(p ^^ 2 - b);<br>
<br>
        for (uint i = si / 2; i < B_SIZE / 2; i += p)<br>
            mark[i] = true;<br>
    }<br>
<br>
    uint pCount = 1; uint lastP = 2;<br>
    // Do something with first prime (2) here.<br>
<br>
    uint[] smallP = [2];<br>
<br>
    bool[B_SIZE / 2] mark = false;<br>
    foreach (immutable uint i; 1 .. B_SIZE / 2) {<br>
        if (!mark[i]) {<br>
            pCount++; lastP = 2 * i + 1;<br>
            // Do something with lastP here.<br>
<br>
            smallP ~= lastP;<br>
            if (lastP ^^ 2 <= B_SIZE)<br>
                crossOut(2 * i + 1, 1, mark);<br>
        } else<br>
            mark[i] = false;<br>
    }<br>
<br>
    for (uint b = 1 + B_SIZE; b < MAX_N; b += B_SIZE) {<br>
        for (uint i = 1; smallP[i] ^^ 2 < b + B_SIZE; ++i)<br>
            crossOut(smallP[i], b, mark);<br>
        foreach (immutable uint i; 0 .. B_SIZE / 2) {<br>
            if (!mark[i]) {<br>
                pCount++; lastP = 2 * i + b;<br>
                // Do something with lastP here.<br>
<br>
                if (lastP <= RT_MAX_N)<br>
                    smallP ~= lastP;<br>
            } else<br>
                mark[i] = false;<br>
        }<br>
    }<br>
<br>
    return tuple(pCount, smallP.length, lastP);<br>
}<br>
<br>
void main() {<br>
    immutable result = calcPrimes;<br>
<br>
    writeln("Found ", result[0], " primes in total.");<br>
    writeln("Recorded ", result[1], " small primes, up to ", RT_MAX_N);<br>
    writeln("Last prime found was ", result[2]);<br>
}<br>
<br>
<br>
Is it a good idea to add a simple but reasonably fast Sieve implementation to Phobos? I have needed a prime numbers lazy range, and a isPrime() function numerous times. (And as for std.numeric.fft, people that need even more performance will use code outside Phobos).<br>


<br>
Bye,<br>
bearophile<br>
</blockquote></div><br></div>