/* 

  Prime Sieve in Picat.

  Port of Trealla's Prolog code samples/sieve.pl
  https://github.com/infradig/trealla/blob/master/samples/sieve.pl
  

  This model was created by Hakan Kjellerstrand, hakank@gmail.com
  See also my Picat page: http://www.hakank.org/picat/

*/

% import v3_utils.

main => go.

go ?=>
  time(test),
  nl.
go => true.

go2 ?=>
  Tests = [test1,test2,test3,test4,test5,test6,test7,test8,test9],
  foreach(Test in Tests)
    println(test=Test),
    time(Test),
    nl
  end,
  
  nl.
go2 => true.


primes(Limit,Ps) :-
    integers(2,Limit,Is),
    sift(Is,Ps).

integers(Low,High,[Low|Rest]) :-
    Low =< High,
    !,
    M is Low+1,
    integers(M,High,Rest).
integers(_,_,[]).

sift([],[]).
sift([I|Is],[I|Ps]) :-
    remove(I,Is,New),
    sift(New,Ps).

remove(_,[],[]) :- !.
remove(P,[I|Is],Nis) :-
    0 is I mod P,
    !,
    remove(P,Is,Nis).
remove(P,[I|Is],[I|Nis]) :-
    X is I mod P,
    X \= 0,
    remove(P,Is,Nis).

test :-
    print('TEST: '),
    primes(100, X),
    X=[2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97],
    print(' PASSED'), nl.
    % , halt.

test1 :- primes(10, X), write(X), nl.
test2 :- primes(100, X), write(X), nl.
test3 :- primes(1000, X), write(X), nl.
test4 :- primes(5000, X), write(X), nl.
test5 :- primes(10000, X), write(X), nl.
test6 :- primes(50000, X), write(X), nl.
test7 :- primes(100000, X), write(X), nl.
test8 :- primes(500000, X), write(X), nl.
test9 :- primes(1000000, X), write(X), nl.