Search code examples
listprolog

Prime numbers Prolog

I have written Prolog code to (try) find prime numbers between 0 and N. I am however unable to filter out composite numbers.

Any advice would be great.

 check(N, 2) :-
     N mod 2 =:= 0.

 plist(N, List) :-
      X>1, 
      findall(Z, between(1, N, Z), L1),
      list(L1, 2, List).

 
 list([], _, []).

 list([H | Tail1], 2, [H | Tail2]) :-
      \+ divide(H, 2),
      list(Tail1, 2, Tail2).

 list([H | Tail1], 2, List) :-
      divide(H, 2),
      list(Tail1, 2, List).
Solution

  • Start coding a predicate is_prime(N) :- .... without any optimization, just looping from 2 to N-1 (of course, you can stop at square root of N, but it's not so important right now...).

    You can test it at the command line, ?- is_prime(13). should give true, ?- is_prime(21). should give false...

    Then you have done:

    plist(N, List) :-
      findall(Z, (between(1, N, Z), is_prime(Z)), List).