links

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

sieve of eratosthenes

Erlang

% Sieve of Erastosthenes whatever in Erlang
% Written by Robert Hoelz
%
% To run, load the Erlang shell (erl), and type the following:
%   c(sieve).
%   sieve:main(<num>).

-module(sieve).
-export([main/1, loop/1, initPrimes/1, buildPrimes/2, buildPrimesLoop/5, removeMultiples/3, nextPrime/3, feedRest/3]).

buildPrimes(Limit, Printer) ->
    buildPrimesLoop(Limit, Printer, initPrimes(Limit), 0, 2).

buildPrimesLoop(Limit, Printer, Primes, Index, CurrPrime) ->
    if
        CurrPrime * CurrPrime > Limit ->
            feedRest(Printer, Primes, 0);
        true ->
            Printer ! CurrPrime,
            ModPrimes = removeMultiples(Primes, CurrPrime, 0),
            buildPrimesLoop(Limit, Printer, ModPrimes, Index + 1, nextPrime(ModPrimes, 0, CurrPrime + 1))
    end.

removeMultiples([], _, _) ->
    [];

removeMultiples([Head|Tail], Base, Index) ->
    if
        Index rem Base == 0 ->
            [0|removeMultiples(Tail, Base, Index + 1)];
        true ->
            [Head|removeMultiples(Tail, Base, Index + 1)]
    end.

nextPrime([], Index, _) ->
    Index;

nextPrime([Head|Tail], Index, CurrPrime) ->
    if
        CurrPrime == Index ->
            if
                Head == 1 ->
                    CurrPrime;
                true ->
                    nextPrime(Tail, CurrPrime + 1, Index + 1)
            end;
        true ->
            nextPrime(Tail, Index + 1, CurrPrime)
    end.

feedRest(Printer, [], _) ->
    Printer ! stop;

feedRest(Printer, [Head|Tail], Index) ->
    if
        Head == 1 ->
            Printer ! Index;
        Head == 0 ->
            true
    end,
    feedRest(Printer, Tail, Index + 1).

initPrimes(Limit) ->
    if
        Limit == 1 ->
            [0, 0];
        true ->
            lists:append(initPrimes(Limit - 1),[1])
    end.

main(Limit) ->
    Printer = spawn(sieve, loop, [self()]),
    buildPrimes(Limit, Printer),
    receive
        done ->
            true
    end.

loop(Pid) ->
    receive
        stop ->
            io:format("~n");
        Num ->
            io:format("~B ", [Num]),
            loop(Pid)
    end,
    Pid ! done.

back to Eratosthenes page

stats

It is Saturday May 17, 2008 11:02 am
This page served 530 times
This page last modified: April 14, 2008 11:28 am
Your IP address is: 38.103.63.17
You are browsing using: CCBot/1.0 (+http://www.commoncrawl.org/bot.html)
You are browsing from: United States.
badcomputer.org's uptime: 11:02:28 up 23 days, 11:44, 0 users, load average: 0.13, 0.12, 0.05