List of primes

[Infty]

Greetings,

I was thinking of a problem to solve in order to practise prolog.

Problem: There is a given number N, I would like to generate list of primes that are (<=N).

So i wrote a few predicats in order to solve this but i dont know how to put them together, everything i tried failed.

Here are my predicates:

Primality test:
prime(N):-T is N//2, not_dividable_by_all(N,T).
not_dividable_by_all(N,T):-T>1, T1 is T-1, N mod T=\=0,not_dividable_by_all(N,T1).
not_dividable_by_all(N,1).

Adding to a list:
There are probably 3 ways, add on the begining add on the end or use concatenation i guess, got all 3 predicates but i will put concatenation here only for now if you think other predicates would be better i will change.
conc([],List,List).
conc([Head|Tail],List2,[Head|Result]):-conc(Tail,List2,Result).

Ok my idea is to recure through N, n1,n2,n3,...,N check if n1 is prime add to a list countinue for n2,n3,...,N

Regards,Vlad

 

[kahleen]

Your prime test is correct, it works fine, it even avoids declaring 1 to be a prime in a smart way (because of the N // 2 feature).

To produce a list of primes <= N, you don't need a general concatenation predicate ... you simply need adding an item in front of a list, which in Prolog is straightforward ... if L is a list, then [X | L] is the same list with X appended in front of it.

To produce a list of primes limited by N, you will write a predicate generate_primes(K, Primes, Result). You launch the algorithm by making K = N and Primes = []. This means that you begin from N and the list of Primes is currently empty. The result is still unbound in variable Result. At each step, you test if K is a prime:
- K is prime, then you add K in front of the Primes list and continue with K-1
- K is not a prime, then you continue with K-1

The process stops when K reaches 1, at which point the Primes list is the Result.

generate_primes(1, Primes, Result) :- Result = Primes, !.
generate_primes(K, Primes, Result) :-
	prime(K), !,   % the ! is needed here so that we don't need to test if K is a prime on the next generate_primes clause
	K1 is K - 1,
	generate_primes(K1, [K | Primes], Result).
generate_primes(K, Primes, Result) :-
	K1 is K - 1,
	generate_primes(K1, Primes, Result).

Now, you can simplify your initial call by writing a delegating predicate that only takes 2 arguments:

generate_primes(N, Result) :-
	generate_primes(N, [], Result).