Sieve of Eratosthenes: Difference between revisions

Content deleted Content added

Inline

@@ Line 13,796: / Line 13,796: @@
 </pre>
-Based on Cloksin&Mellish p.175, modified to stop early:
+Another version, based on Cloksin&Mellish p.175, modified to stop early as well as to work with odds only and use addition in the removing predicate, instead of the <code>mod</code> testing as the original was doing:
-<lang Prolog>p(N,[]):- N < 2, !.
+<lang Prolog>primes(N,[]):- N < 2, !.
-p(N,[2|R]):- i(3,N,L), s(N,L,R).
+primes(N,[2|R]):- ints(3,N,L), sift(N,L,R).
-i(A,B,[A|C]):- A=<B -> D is A+2, i(D,B,C).
+ints(A,B,[A|C]):- A=<B -> D is A+2, ints(D,B,C).
-i(_,_,[]).
+ints(_,_,[]).
-s(_,[],[]).
+sift(_,[],[]).
-s(N,[A|B],[A|C]):- A*A =< N -> r(A,B,D), s(N,D,C)
+sift(N,[A|B],[A|C]):- A*A =< N -> rmv(A,B,D), sift(N,D,C)
-                   ; C=B.
+                      ; C=B.
-r(A,B,D):- M is A*A, r(A,M,B,D).
+rmv(A,B,D):- M is A*A, rmv(A,M,B,D).
-r(_,_,[],[]).
+rmv(_,_,[],[]).
-r(P,M,[A|B],C):- (   M>A ->  C=[A|D], r(P,M,B,D)
+rmv(P,M,[A|B],C):- (   M>A ->  C=[A|D], rmv(P,M,B,D)
-                 ;   M==A ->  M2 is M+2*P, r(P,M2,B,C)
+                   ;   M==A ->  M2 is M+2*P, rmv(P,M2,B,C)
-                 ;   M<A -> M2 is M+2*P, r(P,M2,[A|B],C)
+                   ;   M<A -> M2 is M+2*P, rmv(P,M2,[A|B],C)
-                 ).</lang>
+                   ).</lang>
 ===Using lazy lists===