% generating primes in prolog using the sieve of Eratosthenes % start by generating a data base of numbers number(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 primes(N):-cleanup, generate(N), !, strikeout(N), !, display. cleanup:-abolish(last), abolish(number), abolish(prime), abolish(multiple). display:-prime(P), prin(P), prin(' '),fail. status:-number(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)... scan(Label):- scan(Label, 2, 1). scan(Label,First,Step):-V=First, (Garbage=..[Label,_], Garbage,abolish(Label)|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(last), last(Last),assertz(number(Last)), Last>=N,!, abolish(last). strikeout(N):- number(Prime), print(Prime), assertz(prime(Prime)), multiples(Prime,N), Prime>=N. multiples(Prime, N):- scan(multiple, Prime, Prime), multiple(M), remove(M), M>=N,!, abolish(multiple). remove(M):-number(M),retract(number(M),_),!. remove(M):-true,!. % trace [prime, multiples, multiple]! listing! print('Use primes(P)? to generate primes in range 2..P')!