Witam, mam następujący problem: muszę napisać w Prologu program generujący listę liczb pierwszych, mniejszych lub równych od zadanej przez użytkownika liczby. Znalazłem coś takiego tu:
http://colin.barker.pagesperso-orange.fr/lpa/primes.htm
Tylko jest problem, nie bardzo wiem jak zmienić ten kod aby sprawdzane były również liczby nieparzyste. Pomoże ktoś?
Tylko jest problem, nie bardzo wiem jak zmienić ten kod aby sprawdzane były również liczby nieparzyste
OT: Słabe trochę generowanie liczb pierwszych które sprawdza tylko liczby parzyste (jedyny możliwy wynik to 2 i []).
Zamiast szukać gotowca, lepiej byś wyszedł na myśleniu jak to zrobić samemu ;).
Rozwiązanie które znalazłeś jest mocno przekombinowane (z dobrych powodów jak np. wydajność -> zamiast sprawdzać do N, wystarczy sprawdzać do sqrt(N)).
No więc jak dojść do rozwiązania. Na pewno chcemy mieć jakiś predykat primes_le(N, X), który będzie działał mniej więcej tak:
[debug] 25 ?- primes_le(20, X).
X = [19, 17, 13, 11, 7, 5, 3, 2].
(szukający liczb pierwszych mniejszych lub równych N)
Znamy przypadek dolny
(nie ma liczby pierwszej mniejszej lub równej 1, więc primes_le(1, []).
primes_le(1, []).
A dla N > 1 są dwie możliwości:
-> N jest liczbą pierwszą, więc primes_le N to N oraz primes_le (N-1)
-> N nie jest liczbą pierwszą, więc primes_le N to primes_le (N-1)
Zapisanie tego jest już dość proste:
primes_le(1, []) :- !.
primes_le(N, [N|XS]) :-
is_prime(N),
N1 is N - 1, !,
primes_le(N1, XS).
primes_le(N, XS) :-
N1 is N - 1,
primes_le(N1, XS).
Oraz is_prime dla kompletności:
is_prime(N) :- is_prime1(N, 2), !.
is_prime1(N, M) :-
N mod M > 0,
M1 is M + 1,
is_prime1(N, M1).
is_prime1(N, N).
(Prawie że imperatywna pętla po dzielnikach N, od 2 do N-1. Niezbyt ładne, ale łatwo zmienić na sqrt(N) zwiększając wydajność).
I to tyle. Jeśli chcesz poćwiczyć, warto zrobić jakieś usprawnienie (np: zmiana granicy is_prime na sqrt(N), skakanie tylko po nieparzystych w primes_le, usunięcie zapętlania w nieskończoność przy is_prime(1) i mniejszych, usunięcie pętli nieskończonej przy primes_le(0) i mniejszych, zastanowienie się po co tutaj były użyte odcięcia oraz czy wszystkie są potrzebne, etc).
Sprawdzenie czy działa:
[debug] 28 ?- primes_le(2, X).
X = [2].
[debug] 29 ?- primes_le(2, X).
X = [2].
[debug] 30 ?- primes_le(3, X).
X = [3, 2].
[debug] 31 ?- primes_le(4, X).
X = [3, 2].
[debug] 32 ?- primes_le(10, X).
X = [7, 5, 3, 2].
[debug] 33 ?- primes_le(4, [3, 2]).
true.