numeros - determinar si un numero es primo prolog

Cálculo de si el número es primo en Prolog

Question

Estoy tratando de calcular si la entrada es un número primo, pero algo va mal ... aquí está mi código:

primeNumber(X):-
    prime_prime(A, 1).

prime_prime(A, B):-
    R is A mod B,
    R =:= 1,
    R =:= A.
prime_prime(X, B):-
    B < A,
    Next is B + 1,
    prime_prime(A, Next).

Me da false todo el tiempo ¿Alguien tiene alguna pista o idea sobre lo que estoy haciendo mal?

Answer 1

Kay ya proporcionó una modificación de trabajo del programa roto. Proporcionaré un análisis simple de lo que está roto.

Al resolver un problema en Prolog, es bueno poder escribir lógicamente qué es lo que quieres primero. En este caso, parece que quiere declarar que:

A number, A, is prime if, for each number B < A, the value of A mod B is non-zero.

Probablemente haya un par de maneras de renderizar esto directamente en Prolog, del cual Kay muestra uno.

Sin embargo, de la forma en que se escriben las reglas originales, dicen:

A number, A, is prime if:
    (Rule 1) The value of A mod B, for a given value of B, is 1 and is also A.
 OR (Rule 2) B < A and Rule 1 is satisfied with A and B+1.

Como puede ver, las reglas tal como se definen tienen algunos problemas:

• Las reglas no coinciden con la definición lógica de primo descrita en términos de la relación de módulo entre el número original y todos los números menores que él.
• La primera regla espera una condición matemática imposible cuando A no es igual a 1 (recuerde, la coma [,] en Prolog es una conjunción )
• Las reglas se inician con el divisor inicial de 1, que probablemente sea malo ya que 1 divide todo y es probable que se convierta en una excepción a las reglas que funcionan

EDITAR

Volviendo a la primera definición de un primo utilizando el operador de módulo, podemos traducirlo en Prolog de la siguiente manera:

is_prime(N) :-                 % N is prime if...
  N > 1,                       % N > 1, and
  non_divisible_from(N, 2).    % N is non-divisible by everything from 2 to N-1

non_divisible_from(N, D) :-    % N is non-divisible by D through N-1 if...
  N =< D.                      % D >= N
                               % --OR--
non_divisible_from(N, D) :-    % N is non-divisible from D to N-1 if...
  N > D,                       % N > D, and
  N mod D =/= 0,               % N is non-divisible by D, and
  D1 is D + 1,                 % N is non-divisible by D+1 to N-1
  non_divisible_from(N, D1).

Esta lógica es básicamente la misma que la de Kay, excepto que está usando una construcción Prolog if-then-else.

Answer 2

Ver http://www.swi-prolog.org/pldoc/man?function=mod/2 :

+IntExpr1 mod +IntExpr2
Módulo, definido como Resultado = IntExpr1 - (IntExpr1 div IntExpr2) × IntExpr2, donde div es la división con piso.

Entonces R debería ser 0 . mod tiene solo un resultado

Una solución de trabajo sería:

primeNumber(A) :-
    A > 1,                 % Negative numbers, 0 and 1 are not prime.
    prime_prime(A, 2).     % Begin iteration:

prime_prime(A, B) :-       % Test if A divides by B without remainder
    B >= A                 % The limit was reached?
    ->  true               %     Then it''s prime.
    ;   0 is A mod B       % B divides A without a remainder?
    ->  false              %     Then it''s not prime.
    ;   succ(B, C),        % Otherwise: C is B + 1
        prime_prime(A, C). % Test if C divides A.

Por cierto, primeNumber/1 (un predicado llamado primeNumber , con un argumento) es un predicado totalmente separado de primeNumber/2 (mismo nombre, dos argumentos). Una "subfunción" que solo obtiene un argumento adicional para el valor inicial, generalmente recibe el mismo nombre. Por lo tanto, en lugar de prime_prime solo debes usar primeNumber , aunque en Prolog normalmente no usas camelCase.

Utilizando la optimización que Sergei Lodyagin propuso en los comentarios:

primeNumber(A) :-
    A > 1,                    % Negative numbers, 0 and 1 are not prime.
    sqrt(A, L),               % A prime factor of A is =< the square root of A.
    prime_prime(A, 2, L).     % Begin iteration:

prime_prime(A, B, L) :-       % Test if A divides by B without remainder
    B >= L                    % The limit was reached?
    ->  true                  %     Then it''s prime.
    ;   0 is A mod B          % B divides A without a remainder?
    ->  false                 %     Then it''s not prime.
    ;   succ(B, C),           % Otherwise: C is B + 1
        prime_prime(A, C, L). % Test if C divides A.

Y si usa el predicado predefinido between(+Low, +High, ?Value) :

primeNumber(A) :-
    L is floor(sqrt(A)),
    /+ (between(2, L, X),
        0 is A mod X).

Y para reducir el número de iteraciones aún más, solo necesita probar módulos impares:

primeNumber(2).
primeNumber(A) :-
    A > 2,
    /+ 0 is A mod 2,
    L is floor(sqrt(A) / 2),
    /+ (between(1, L, X),
        0 is A mod (1 + 2*X)).