generate a list of prime numbers

[nn987]

hi all

how can I generate a list of Prime numbers until N.
i.e
primes(20,L).
[2,3,5,7,11,13,17,19]

thanks.

 

[joel76]

You can use the sieve of Eratosthenes
You create a list L1 of numbers from 2 to N.
You add the first number N of this list in the list of prime numbers LP, you clean the list L1 of all multiples of N and you recurse with the new list L1 and the new list LP.

 

[nn987]

%Create a list of prime numbers

%divisible(X,Y):- Y=<X,X mod Y =:= 0.
%divisble(X,Y):- Y < X, Y1 is Y + 1, divisible(X,Y1).

%divisible(10,2).
divisible(X,Y):- N is Y*Y,N =< X,X mod Y =:= 0.
divisible(X,Y):- Y < X, Y1 is Y + 1, divisible(X,Y1).

%isprime([3],Z).
isprime([X|_],X):-Y is 2, X >1, \+divisible(X,Y).
isprime([_|T],Z):-isprime(T,Z).

%put into a list of N numeros.
%genList(10,L).
genList(0,[]).
genList(N,[X|Xs]):- N > 0,
X is N+1,
N1 is N-1,genList(N1,Xs).

%calculate prime numbers until N
%ie lstPrimes(20,C).
lstPrimes(N,C):-genList(N,X),isprime(X,C).

 

[joel76]

You have a bug :
2 ?- lstPrimes(100,C).
C = 101 ;