:- module(_, _, [functional,loops,arrays]).
:- use_module(library(arrays/arrays_log)).

% Prime numbers up to N, using Eratosthenes sieve.
% Coded using the functional, loops, and arrays packages.

primes(N) := Res :-
    % Initialize the array with n+1 values to access until index n
    A = ~new_array_log,
    for (I in 2 .. N) { A[I] := true },
    % We cross out the non primes
    for (I in 2 .. ~floor(sqrt(N))) { % Loop goes until square root of N
        if (A[I] == true) { % If a[i] is prime we cross out its multiples
            for (J in I*I .. I .. N) { A[J] := false }
        }
    },
    % We take the primes from the sieve and put them into a list
    Res = ResTail,
    for (K in 2 .. N) {
        if (A[K] == true) { accum(!ResTail,K) }
    },
    ResTail = [].

accum(!R, X) :- R = [X|Tail], R := Tail.

% Try:
% ?- primes(10, Ps).
% ?- primes(100, Ps).
% ?- primes(10000, _L), length(_L,MPrimes).