| /* VAX C-Prolog Benchmark Package */ |
| /* Copyright 1985 by Tektronix, Inc., and Portland State University */ |
| |
| |
| /* The sieve of Erastosthenes. */ |
| /* */ |
| /* Benchmark prolog program which requires the upper limit as a */ |
| /* parameter, and will find all prime numbers between 1 and upper */ |
| /* bound. Execution time is given in milliseconds. */ |
| /* */ |
| |
| primes(Limit, Prime_nums) :- |
| integer_list(2,Limit,Ints), |
| sift(Ints,Prime_nums). |
| |
| integer_list(Low,High,[Low|Rest]) :- |
| Low =< High, !, |
| M is Low + 1, |
| integer_list(M,High,Rest). |
| |
| integer_list(_,_,[]). |
| |
| sift([],[]). |
| |
| sift([Int|Ints],[Int|Primes]) :- |
| remove(Int,Ints,New), |
| sift(New,Primes). |
| |
| remove(Prime,[],[]). |
| |
| remove(Prime,[Int|Ints],[Int|New_ints]) :- |
| \+(0 is Int mod Prime), !, |
| remove(Prime,Ints,New_ints). |
| |
| remove(Prime,[Int|Ints],New_ints) :- |
| 0 is Int mod Prime, !, |
| remove(Prime,Ints,New_ints). |
| |
