links

< home >
< unix stuff >
< code >
< writing >
< archive >
< music >
< photos >
< recipes >
< site map >
< about badcomputer >

The sieve of eratosthenes

D

/* Sieve of Eratosthenes in D
 * Written by Rob Hoelz
 */

import std.stdio;
import std.string;


void removeMultiples(int[] primes, int base) {
    int mult = base * 2;

    while(mult < primes.length) {
        primes[mult] = 0;
        mult += base;
    }
}

int nextPrime(int[] primes, int currPrime) {
    for(int i = currPrime + 1; i < primes.length; i++) {
        if(primes[i]) {
            return i;
        }
    }
    return primes.length;
}

void generatePrimes(int[] primes) {
    long currPrime = 2;

    while((currPrime * currPrime) < primes.length) {
        removeMultiples(primes, currPrime);
        currPrime = nextPrime(primes, currPrime);
    }
}

int main(char [][] args) {
    int[] primes;

    if(args.length > 1) {
        long limit = atoi(args[1]);
        primes = new int[limit + 1];
        primes[0] = primes[1] = 0;
        for(int i = 2; i <= limit; i++) {
            primes[i] = 1;
        }

        generatePrimes(primes);
        foreach(index, isPrime; primes) {
            if(isPrime) {
                writef("%d ", index);
            }
        }
        writefln("");
    }
    return 0;
}

back to Eratosthenes page

stats

It is Friday December 05, 2008 10:48 am
This page served 952 times
This page last modified: April 14, 2008 11:28 am
Your IP address is: 38.103.63.61
You are browsing using: CCBot/1.0 (+http://www.commoncrawl.org/bot.html)
You are browsing from: United States.
badcomputer.org's uptime: 10:48:55 up 24 days, 14:59, 2 users, load average: 0.00, 0.00, 0.00