Generating A List Of Prime Numbers

Question

I need to generate a list of prime numbers in a given range (between 1 and N). I developed an algorithm to check whether an given number is prime and it is working fine. The problem is in the function that checks all numbers in the range and print them. Here's what I developed so far...

% P39 (*) A list of prime numbers. 
% Given a range of integers by its lower and upper limit, construct a 
% list of all prime numbers in that range.

:- ensure_loaded(p31).   % make sure is_prime/1 is loaded

% prime_list(A,B,L) :- L is the list of prime number P with A <= P <= B

prime_list(A,B,L) :- A =< 2, !, p_list(2,B,L).
prime_list(A,B,L) :- A1 is (A // 2) * 2 + 1, p_list(A1,B,L).

p_list(A,B,[]) :- A > B, !.
p_list(A,B,[A|L]) :- is_prime(A), !, 
   next(A,A1), p_list(A1,B,L). 
p_list(A,B,L) :- 
   next(A,A1), p_list(A1,B,L).

next(2,3) :- !.
next(A,A1) :- A1 is A + 2.

Thanks in advance :)

Answer 1

Good job on the prime testing. Your loop, however, is both more code than you need and kind of off-track. Based on the code sample you show, you probably want this:

generatePrime(X, Y, N) :-
  between(X, Y, N),
  isPrime(N).

See how this works?

?- generatePrime(2, 10, X).
X = 2 ;
X = 3 ;
X = 5 ;
X = 7 ;
false.

Those ; are interactively given by the human operator.

If you want to print all of them out, you could go with a classic failure driven loop like so:

generatePrime(X, Y) :-
  between(X, Y, N),
  isPrime(N),
  write(N), nl, 
  fail.
generatePrime(_, _).

I wouldn't recommend this, but failure-driven loops seem to be a hot topic for beginners for some reason. I'd be more inclined to do something like this:

generatePrimes(X, Y) :-
  forall(
    (between(X, Y, N), isPrime(N)),
    (write(N), nl))).

Either way you're basically there, and you have a lot of options.

Now, a few special notes:

1. isPrime(2). is basically equivalent to what you have with isPrime(2) :- true, !. I would recommend staying away from the cut while you're just getting started. And you almost never really need an explicit true.
2. not/1 is not ISO. Use \+/2 instead (i.e. \+ divisible(X, 2))
3. X is 1 is no better than X = 1. is/2 is only necessary if you have an expression on the right-hand side you want evaluated and stored in the variable named on the left-hand-side. Other calling conventions for is/2 either don't work or aren't productive.
4. X is X+1 will always fail. Prolog has variables, not assignables. You cannot change the value of a variable ever. You can only arrange for a binding somewhere else to have a particular value, perhaps recursively. In this case, the right thing to do is X1 is X+1, generatePrime(Y, X1). Most, but not all, expected uses of assignment can be handled similarly to this.
5. I am skeptical that isPrime(X) -> write(X) ; true will do the right thing without being surrounded by parentheses; this is an area of Prolog's syntax that usually trips me up, so I almost always wind up parenthesizing the whole conditional expression to get it right. Also, I don't think you need ; true on there.

Answer 2

divisible(X,Y) :- 0 is X mod Y, !.
divisible(X,Y) :- X > Y+1, divisible(X, Y+1).

isPrime(2) :- true,!.
isPrime(X) :- X < 2,!,false.
isPrime(X) :- not(divisible(X, 2)).

primeR(A,B):- A =< B,(isPrime(A)->print(A), write(' '),A1 is A + 1; A1 is A + 1),primeR(A1,B).

Output:

?- [primet]. 
true.

?- primeR(1,20).
2 3 5 7 11 13 17 19
false.