links

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

The sieve of eratosthenes

Dylan

Module: sieve
Author: Rob Hoelz
Synopsis: The Sieve of Eratosthenes in Dylan

define class <sieve> (<object>)
    slot limit :: <integer>;
    slot primes :: <sequence>;
end class <sieve>;

define method initialize(s :: <sieve>, #key limit = 0)
    s.limit := limit;
    s.primes := make(<range>, from: 2, to: limit);
end method;

define function genAux(sieves :: <sequence>, limit :: <integer>)
    => (result :: <sequence>)
    let x = first(sieves);
    if ((x * x) <= limit)
        let xs = remove(sieves, x, count: 1);
        add(genAux(choose(method(y) modulo(y, x) ~== 0 end method, xs), limit), x);
    else
        sieves;
    end if;
end function;

define method generate(s :: <sieve>) => ();
    s.primes := genAux(s.primes, s.limit);
end method;

define method printPrimes(s :: <sieve>) => ();
    map (method(x) format-out("%d ", x) end, s.primes);
    format-out("\n");
end method;

define function atoi(str :: <string>) => (result :: <integer>)
    let i = 0;
    let sum = 0;

    while(i < str.size)
        sum := sum * 10;
        sum := sum + (as(<integer>, element(str, i)) - as(<integer>, '0'));
        i := i + 1;
    end while;
    sum;
end function;


define function main(argv0, #rest args)
    let s = make(<sieve>, limit: atoi(first(args)));
    generate(s);
    printPrimes(s);
end function main;

main(application-name(), first(application-arguments()));

back to Eratosthenes page

stats

It is Monday September 08, 2008 1:02 am
This page served 792 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: 01:02:35 up 39 days, 16:09, 2 users, load average: 0.03, 0.05, 0.01