% ---------------------------------------------------------------------------- %
% sieve.m
% Ralph Becket <rbeck@microsoft.com>
% Mon Jan  8 14:23:22 GMT 2001
% vim: ts=4 sw=4 et tw=0 wm=0 ff=unix
%
% Eratosthenes' Sieve - counts the number of primes in 2..8192
%
% ---------------------------------------------------------------------------- %

:- module mytest.

:- interface.

:- import_module io.



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



:- implementation.

:- import_module int, bool, array, string, list, require, benchmarking.



main -->
    io__command_line_arguments(ArgV),
    (   { ArgV = [],        Repeats = 1 }
    ;   { ArgV = [Arg],     Repeats = string__det_to_int(Arg) }
    ;   { ArgV = [_,_|_],   error("usage: sieve [NumIterations]") }
    ),
    { P = ( pred(Sz::in, N::out) is det :- N = count_primes(Sz) ) },
    { benchmarking__benchmark_det(P, 8192, Count, Repeats, Time) },
    io__format("Count: %d\n", [i(Count)]).



:- func count_primes(int) = int.

count_primes(Size) = sieve_and_count(2, array__init(Size, yes), 0).



:- func sieve_and_count(int, array(bool), int) = int.
:- mode sieve_and_count(in, array_di, in) = out is det.

sieve_and_count(I, A, N) =
    (      if I > array__max(A)         then N
      else if array__lookup(A, I) = no  then sieve_and_count(I + 1, A, N)
      else    sieve_and_count(I + 1, filter_multiples(I + I, I, A), N + 1)
    ).



:- func filter_multiples(int, int, array(bool)) = array(bool).
:- mode filter_multiples(in, in, array_di) = array_uo is det.

filter_multiples(I, P, A) =
    ( if I > array__max(A)
      then A
      else filter_multiples(I + P, P, array__set(A, I, no))
    ).