Prolog Find N prime numbers
I have a problem with the recursive function of Prolog. I believe I am not implementing it right and need help.
I need to generate the first N prime numbers and return it in a list. Generating the prime number is not an issue, but rather, generating it in a list is the issue I have.
This is the part of the relevant code:
genList(_, 0, _).
genList(X, N, PrimeList, PrimeList):-
N > 0,
isprime(X),
X1 is X +1,
N1 is N -1,
genList(X1,N1,[X|PrimeList], [X|PrimeList]),!.
genList(X, N, PrimeList, PrimeList):-
N>0,
+isprime(X),
X1 is X + 1,
genList(X1,N,PrimeList, PrimeList).
This is what I type into the Prolog interpreter:
genList(1,N, [],L).
For the 1st line, how do I make the base case such that when N=0 , I stop recursing? Is this correct?
As for the next 2 clauses, I am having difficulty in thinking in terms of logic programming. I definitely feel that this is not logic programming style.
I want to say that when isPrime(X) fails, we continue to the next number without saving anything, but when isPrime(X) is true, then we recurse and continue to the next number, saving X .
How do I do that in Prolog?
First of all, you shouldn't need 4 arguments to your main predicate if you only want two. Here you want the list of the first primes up to N . So an argument for N and an argument for the list should be enough:
primeList(N, L) :-
% eventually in the body a call to a worker predicate with more arguments
Now here, your logic is explained in those terms:
primeList(N, [N|L]) :-
% If we're not at the base case yet
N > 0,
% If N is a prime
isPrime(N),
NewN is N - 1,
% Let's recurse and unifie N as the head of our result list in the head
% of the predicate
primeList(NewN, L).
primeList(N, L) :-
% Same as above but no further unification in the head this time.
N > 0,
% Because N isn't a prime
+ isPrime(N),
NewN is N - 1,
primeList(NewN, L).
To that you'd have to add the base case
primeList(0, []).
You could rewrite that with cuts as follows:
primeList(0, []) :- !.
primeList(N, [N|L]) :-
isPrime(N),
!,
NewN is N - 1,
primeList(NewN, L).
primeList(N, L) :-
NewN is N - 1,
primeList(NewN, L).
Here's what you meant to write:
genList(N, L) :- genList(2, N, L, []).
genList(X, N, L, Z):- % L-Z is the result: primes list of length N
N > 0 ->
( isprime(X) -> L=[X|T], N1 is N-1 ; L=T, N1 is N ),
X1 is X + 1,
genList(X1,N1,T,Z)
;
L = Z.
The if-then-else construct embodies the cuts. And you're right, it's essentially a functional programming style.
We can introduce a little twist to it, disallowing requests for 0 primes (there's no point to it anyway), so that we also get back the last generated prime:
genList(1, [2], 2) :- !.
genList(N, [2|L], PN) :- N>1, L=[3|_], N2 is N-2, gen_list(N2, L, [PN]).
gen_list(N, L, Z) :- L=[P|_], X is P+2, gen_list(X, N, L, Z).
gen_list(X, N, L, Z) :- % get N more odd primes into L's tail
N > 0 ->
( isprime(X) -> L=[_|T], T=[X|_], N1 is N-1 ; L=T, N1 is N ),
X1 is X + 2,
gen_list(X1,N1,T,Z)
;
L = Z. % primes list's last node
Run it:
?- genList(8,L,P).
L = [2, 3, 5, 7, 11, 13, 17, 19]
P = 19
This also enables us to stop and continue the primes generation from the point where we stopped, instead of starting over from the beginning:
?- L = [3|_], gen_list(8, L, Z), Z=[P10|_], writeln([2|L]),
gen_list(10, Z, Z2), Z2=[P20], writeln(Z).
[2, 3, 5, 7, 11, 13, 17, 19, 23, 29|_G1037]
[29,31,37,41,43,47,53,59,61,67,71]
P10 = 29
P20 = 71
下一篇: Prolog找到N个素数