A prime generator in plain Prolog. It skips most composite numbers before testing them, using the fact that every prime above 3 is one more or one less than a multiple of 6, and then tries divisors only up to the square root.
Run it in the playground · Source
List every prime number up to 1000, in order.
Testing every number against every smaller one would work, but it wastes time on numbers that are obviously even or multiples of 3. The program avoids generating those at all.
prime_under(Limit, 2) :-
(Limit >= 2).
prime_under(Limit, 3) :-
(Limit >= 3).
prime_candidate(Current, High, _, Current) :-
(Current =< High).
prime_candidate(Current, High, Step, Value) :-
(Current < High),
(Next is Current + Step),
(NextStep is 6 - Step),
!,
prime_candidate(Next, High, NextStep, Value).
Starting at 5 and stepping by 2, then 4, then 2, … gives 5, 7, 11, 13, 17, 19, …: exactly the numbers of the form 6k − 1 and 6k + 1. Every larger multiple of 2 or 3 is skipped.
prime_from(N, Divisor, _) :-
(Divisor * Divisor > N).
prime_from(N, Divisor, Step) :-
(Divisor * Divisor =< N),
(N mod Divisor =\= 0),
(Next is Divisor + Step),
(NextStep is 6 - Step),
!,
prime_from(N, Next, NextStep).
primes(Limit, Ps) :-
want_primes(Limit),
findall(P, prime_under(Limit, P), Ps).
A candidate is prime if no divisor from the same wheel divides it, up to its
square root: a composite number always has a factor no larger than that.
findall/3 collects all primes into one list.
eyeprolog examples/sieve.pl
primes(1000, [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, 101, …, 991, 997]).
One answer: a list of the 168 primes below 1000 (shortened here; see the full output).
step(want_primes(1000), fact(1), [], []).
The proof is three steps: primes/2 by its rule, the want_primes(1000) fact
above, and one collected step that records the whole result of
findall(P, prime_under(1000, P), …). The proof does not list 168 separate
primality arguments; it treats the collection as a single conclusion.
condition('C1', resolution, ok, 2).
condition('C6', boundary_consistency, ok, 0).
trusted(1).
verdict(checked_with_obligations).
The checker verifies the two rule and fact steps. The findall/3 result is a
trusted boundary: confirming that the list contains all primes and only
primes would mean redoing the search, which a checker never does. The verdict
checked_with_obligations records that the list itself is taken as given.
want_primes(1000) to want_primes(100). You get the 25 primes
below 100.prime_count(N) :- primes(_, Ps), length(Ps, N). to count them.prime_from/3. Do the answers change?Learn more in The Art of EyeProlog, Chapters 6 and 8.