CODEWITHSUNDEEP
prologsieve-of-eratosthenes
mrMoonpenguin
mrMoonpenguin

Reputation: 57

Prolog - Trouble with implementing the Sieve of Eratosthenes

I'm trying to write a program in prolog that finds all prime numbers up to a limit N, I'm trying to achieve this by using the Sieve of Eratosthenes. I'm very new to prolog so I haven't really mastered the art of thinking recursively (you can probably see that in my code).

Nonetheless, I (more or less) tried implementing the algorithm in prolog, but didn't get very far as you'll see here:

 allPrimes(N, Primes) :-
     numlist(2, N, Numlist),
     A is round(sqrt(N)),
     foreach(between(2, A, _i), sift(_i, Numlist, Primes)).

 sift(_i, Numlist, Primes) :-
     findall(_j, (member(_j, Numlist), _j \== _i, (_j mod _i =:= 0)), L),
     subtract(Numlist, L, Primes).

I keep getting false as output because subtract(Numlist, L, Primes) fails, my guess as to why it fails is because Primes has already been instantiated and its value can't be changed. I have tried solving this in other ways, but couldn't come up with a solution.

Any help in guiding me in the right direction is very much appreciated!

Upvotes: 1

Views: 711

Answers (1)

gusbro
gusbro

Reputation: 22585

You cannot change the list of primes after you instantiated it. You may however further instantiate some items on it if they were uninstantiated (not your case) and you could probably solve this problem that way.

Here goes a recursive solution based on your algorithm:

allPrimes(N, Primes) :-
    numlist(2, N, Numlist),
    Stop is round(sqrt(N)),
    allPrimes(Numlist, Stop, Primes).
    
allPrimes([N|Numlist], Stop, [N|Primes]):-
  exclude(is_multiple(N), Numlist, MPrimes),
  (N =< Stop -> allPrimes(MPrimes, Stop, Primes) ; Primes=MPrimes).
  
is_multiple(N, I):-
  I mod N =:= 0.

So you build a list of possible integers and compute the stop number. Then you call the recursive procedure allPrimes/3 which takes the first prime, then excludes all the multiples of that number from the list and recursively calls itself with the remaining elements. After finishing the recursion (base case is when N is the stop number) we build back the prime list.

Sample run:

?- allPrimes(100, Primes).
Primes = [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].

Upvotes: 5

Related Questions