%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%
%% Sieve of eratosthenes to compute primes
%% thom fruehwirth 920218-20, 980311
%% christian holzbaur 980207 for Sicstus CHR
%%
%% ported to hProlog by Tom Schrijvers 
%% translated into AR by N.F. Zhou, 2006

:-include('chr_lib.pl').

main :-
	main(2500).

main(N):-
	cputime(X),
	candidate(N),
	cputime( Now),
	Time is Now-X,
	write(bench(primes ,N,Time,0,bp_ar)), write('.'),nl.

%%% candidate(1) <=> true.
%%% candidate(N) <=> prime(N), N1 is N - 1, candidate(N1).
:-mode candidate(+).
candidate(1) => true.
candidate(N) => prime(N),N1 is N - 1, candidate(N1).

:-mode prime(+).

prime(N):-
    Constr=prime(Flag,N),  
    global_heap_get(prime_1_1,C1),  /* for prime(X) */
    global_heap_get(prime_1_2,C2),  /* for prime(Y) */
    post_event(C1,Constr),
    post_event(C2,Constr),
    prime_1_1(C1,Flag,N),
    prime_1_2(C2,Flag,N).

%%% prime(Y) \ prime(X) <=> 0 =:= X mod Y | true.
prime_1_1(C,Flag,X),var(Flag),{ins(Flag),event(C,Q)} =>
    Q=prime(FlagQ,Y),
    (var(FlagQ)->
       (X mod Y =:= 0-> Flag=1; 
        true)   
     ;
        true
     ).
prime_1_1(C,Flag,X) => true.


prime_1_2(C,Flag,Y),var(Flag),{ins(Flag),event(C,Q)} =>
    Q=prime(FlagQ,X),
    (var(FlagQ)->
       (X mod Y =:= 0-> FlagQ=1; 
        true)   
     ;
        true
     ).
prime_1_2(C,Flag,Y) => true.