/* 

  primes benchmark in Picat v3.

  From SICStus Prolog benchmark https://sicstus.sics.se/performance.html


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

*/

main => go.

go ?=>
  data(Data),
  primes(Data,Out),
  println(Out),
  
  nl.

go => true.


top :-
   data(Data),
   primes(Data, _Out).

%	pri2

benchmark(Data, Out) :-
	primes(Data, Out).

data(98).

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(_P,[],[]).
remove(P,[I | Is], Nis0) :-
	I mod P =\= 0, !,
	Nis0 = [I | Nis],
	remove(P,Is,Nis).
remove(P,[_I | Is], Nis) :-
	remove(P,Is,Nis).