sistemas - Programa Prolog para verificar si un número es primer

sintaxis de prolog

Question

Escribí el siguiente programa basado en la lógica de que un número primo solo es divisible por 1 y por sí mismo. Así que simplemente sigo el proceso de dividirlo entre todos los números que son más de uno y menos que sí mismo, pero parece que tengo un problema ya que obtengo todos los números ingresados ​​como verdaderos. Aquí está mi código ...

divisible(X,Y) :-
Y < X,
X mod Y is 0,
Y1 is Y+1,
divisible(X,Y1).
isprime(X) :-
integer(X),
X > 1,
/+ divisible(X,2).

Gracias por adelantado :)

Answer 1

X mod Y is 0 siempre falla, porque no se permiten expresiones a la izquierda de is .

Cambiar a 0 is X mod Y , o, mejor, a X mod Y =:= 0

Answer 2

Soy un principiante en Prolog pero logré solucionar tu problema.

divisible(X,Y) :- 0 is X mod Y, !.
divisible(X,Y) :- X > Y+1, divisible(X, Y+1).
isPrime(2) :- true,!.
isPrime(X) :- X < 2,!,false.
isPrime(X) :- not(divisible(X, 2)).

El problema principal fue la declaración X mod Y is 0 . Predicado tiene dos argumentos (izquierdo y derecho), pero el argumento de la izquierda tiene que ser una constante o una variable que ya está unificada en el momento en que se está ejecutando el predicado. Acabo de intercambiar estos valores. El resto del código es para verificar el número 2 (que es el número primo) y el número menor que 2 (que no son números primos)

Olvidé mencionar que la comparación Y < X tiene errores, porque quiere probar todos los números entre 2 y X-1, esa comparación incluye X.

Answer 3

Creo que es una manera elegante:

isPrime(A):-not((A1 is A-1,between(2,A1,N), 0 is mod(A,N))),not(A is 1).

1 NO ES PRIME NUMBER, pero si no lo crees, simplemente elimina no (A es 1) .

Answer 4

Esta respuesta es una continuación de la respuesta previa de @ lefunction .

isPrime2/1 está lo más cerca posible de isPrime1/1 con algunos cambios cruciales (resaltados a continuación):

isPrime2(2) :- !. isPrime2(3) :- !. isPrime2(X) :- X > 3, X mod 2 =/= 0, N_max is ceiling(sqrt(X)), isPrime2_(X,3,N_max). isPrime2_(X,N,N_max) :- ( N > N_max -> true ; 0 =/= X mod N, M is N + 2, isPrime2_(X,M,N_max) ).

¡Vamos a preguntar!

?- time(isPrime1(99999989)). % 99,999,990 inferences, 5.082 CPU in 5.078 seconds (100% CPU, 19678881 Lips) true. ?- time(isPrime2(99999989)). % 20,002 inferences, 0.001 CPU in 0.001 seconds (100% CPU, 13615185 Lips) true.

Answer 5

La respuesta aceptada de agarwaen no funciona bien en números grandes. Esto se debe a que no es cola recursiva (creo). Además, puede acelerar todo con algunos datos sobre números primos.

1) 2 es el único número primo par

2) Cualquier número mayor que la mitad del original no se divide de manera uniforme

isPrime1(2) :-
!.
isPrime1(3) :-
!.
isPrime1(X) :-
X > 3,
( 0 is X mod 2
-> false
; Half is X/2,
isPrime1_(X,3,Half)
).
isPrime1_(X,N,Half) :-
( N > Half
-> true
; 0 is X mod N
-> false
; M is N + 2,
isPrime1_(X,M,Half)
).

1 ?- time(isPrime1(999983)). % 1,249,983 inferences, 0.031 CPU in 0.039 seconds (80% CPU, 39999456 Lips) true.

EDIT1

¿Es posible dar un paso más? isPrime_/3 es más eficiente que isPrime2/1 porque solo se compara con los primos conocidos anteriormente. Sin embargo, el problema es generar esta lista.

allPrimes(Max,Y) :-
allPrimes(3,Max,[2],Y).
allPrimes(X,Max,L,Y) :-
Z is X+2,
N_max is ceiling(sqrt(X)),
( X >= Max
-> Y = L;
( isPrime_(X,L,N_max)
-> append(L,[X],K), %major bottleneck
allPrimes(Z,Max,K,Y)
; allPrimes(Z,Max,L,Y)
)).
isPrime_(_,[],_).
isPrime_(X,[P|Ps],N_max) :-
( P > N_max
-> true %could append here but still slow
; 0 =/= X mod P,
isPrime_(X,Ps,N_max)
).