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)
    ).