links

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

The sieve of eratosthenes

Mercury

% Sieve of Eratosthenes in Mercury
% Written by Rob Hoelz

:- module sieve.

:- interface.

:- import_module io.
:- import_module list.

:- pred main(io__state, io__state).
:- mode main(di, uo) is det.

:- pred primes(list(int), int, list(int)).
:- mode primes(in, in, out) is det.

:- implementation.

:- import_module int, string.

:- pred range(int, int, list(int)).
:- mode range(in, in, out) is det.

:- pred rangeAux(int, int, list(int), list(int)).
:- mode rangeAux(in, in, out, in) is det.

:- pred primesAux(list(int), int, list(int), list(int)).
:- mode primesAux(in, in, out, in) is det.

:- pred removeMultiples(list(int), int, list(int)).
:- mode removeMultiples(in, in, out) is det.

:- pred removeMultiplesAux(list(int), int, list(int), list(int)).
:- mode removeMultiplesAux(in, in, out, in) is det.

:-  pred getLimit(int, io__state, io__state).
:-  mode getLimit(out, di, uo) is det.

range(Start, Stop, List) :-
    rangeAux(Start, Stop, List, []).

rangeAux(Start, Stop, List, Acc) :-
    (if Start = Stop then
        reverse([Start|Acc], List)
    else
        rangeAux(Start + 1, Stop, List, [Start|Acc])
    ).

primes(In, Limit, Out) :-
    primesAux(In, Limit, Out, []).

primesAux(Primes, Limit, List, Acc) :-
    (if [H|T0] = Primes then
        (if (H * H) > Limit then
            reverse(Acc, Rev),
            append(Rev, [H|T0], List)
        else
            removeMultiples(T0, H, T1),
            primesAux(T1, Limit, List, [H|Acc])
        )
    else
        List = Acc
    ).

% In case you're wondering why I wrote this predicate
% and didn't use list__filter.  It's because filter
% was causing stack overflow with large limits. =(

removeMultiples(In, Base, Out) :-
    removeMultiplesAux(In, Base, Out, []).

removeMultiplesAux([], _, Out, Acc) :-
    reverse(Acc, Out).

removeMultiplesAux([H|T0], Base, Out, Acc) :-
    (if (H mod Base = 0, H \= Base) then
        removeMultiplesAux(T0, Base, Out, Acc)
    else
        removeMultiplesAux(T0, Base, Out, [H|Acc])
    ).

getLimit(Limit) -->
    io__command_line_arguments(Args),
    (if { [LimitStr|_Tail] = Args } then
        ( if { base_string_to_int(10, LimitStr, X) } then
            { Limit = X }
        else
            { Limit = 0 }
        )
    else
        { Limit = 0 }
    ).

main -->
    getLimit(Limit),
    { range(2, Limit, List),
      primes(List, Limit, Primes) },
    io__write_list(Primes, " ", io__write_int),
    io__nl.

back to Eratosthenes page

stats

It is Saturday May 17, 2008 10:50 am
This page served 534 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: 10:50:34 up 23 days, 11:32, 0 users, load average: 0.00, 0.00, 0.00