project euler #10: optimization with primes

bearophile bearophileHUGS at lycos.com
Tue Mar 31 22:28:05 PDT 2009


Michael P. Wrote:

> But for 2 million, it takes quite a while, and an FAQ on the page said most problems are made with being run within a minute. Mine was gonna quite a bit longer.

This will not give you much practice in programming, but if you need primes quickly you may use my xprimes:
http://www.fantascienza.net/leonardo/so/dlibs/primes.html
The code is here, but the basic routine isn't mine, I have just translated it to D:
http://www.fantascienza.net/leonardo/so/libs_d.zip
You will never find faster D code to generate primes. Yet, there are ways to make that D code twice faster (mostly pulling out out of an opApply, but then you can't use the nice foreach syntax).

The following code runs in 2.37 s on a Core 2 at 2 GHz:

import d.primes, d.string;
void main() {
    long tot;
    foreach (p; xprimes(1_000_000_000))
        if (p < 1_000_000_000)
            tot += p;
        else
            break;

    putr(tot);
}

The correct result:
24739512092254535

(With N= 2 millions it takes "nothing", I am not able to time it).

Shorter version, that runs in about 2.8 seconds:

import d.func, d.primes, d.string;
void main() {
    const int N = 1_000_000_000;
    putr( sum(xtakeWhile((int i){ return i < N;}, xprimes(N))) );
}

Bye,
bearophile


More information about the Digitalmars-d-learn mailing list