Tek-Tips is the largest IT community on the Internet today!

Members share and learn making Tek-Tips Forums the best source of peer-reviewed technical information on the Internet!

  • Congratulations Mike Lewis on being selected by the Tek-Tips community for having the most helpful posts in the forums last week. Way to Go!

generate a list of prime numbers

Status
Not open for further replies.

nn987

Programmer
Feb 4, 2006
37
GB
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.
 
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.
 
%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).
 
Status
Not open for further replies.

Part and Inventory Search

Sponsor

Back
Top