% generating primes in prolog using the sieve of Eratosthenes % start by generating a data base of natural numbers natural(i) for i = 2..N % repeatedly take the first as a prime and strike out its multiples % Afterwards if P is a Prime between 2 and N (inclusive) then prime(P) will % be in the database :-style_check(-singleton). :-dynamic(lastnumber/1). :-dynamic(natural/1). :-dynamic(prime/1). :-dynamic(multiply/1). prin(X):-write(X). primes(N):-cleanup, generate(N), !, strikeout(N), !, display. cleanup:-abolish(lastnumber,1), abolish(natural,1), abolish(prime,1), abolish(multiple,1). display:-prime(P), prin(P), prin(' '),fail. status:-natural(N), prin(N), prin(' '),fail. % Scanning the integers scan the next with a property % use like this: scan(i,First),i(I), Until,abolish(i,1)... scan(Label):- scan(Label, 2, 1). scan(Label,First,Step):-V=First, (Garbage=..[Label,_], Garbage,abolish(Label,1); true), Count=..[Label,V], asserta(Count). scan(Label,First,Step):-Count=..[Label,V], retract(Count,_), Next is V+Step, Count2=..[Label,Next], asserta(Count2). generate(N):- scan(lastnumber), lastnumber(Last),assertz(natural(Last)), Last>=N,!, abolish(lastnumber,1). strikeout(N):- natural(Prime), write(Prime), nl, assertz(prime(Prime)), multiples(Prime,N), Prime>=N. multiples(Prime, N):- scan(multiple, Prime, Prime), multiple(M), remove(M), M>=N,!, abolish(multiple,1). remove(M):-natural(M),retract(natural(M),_),!. remove(M):-true,!. % trace [prime, multiples, multiple]! :-listing. :- write('Use primes(P). to generate primes in range 2..P'), nl.