Проверка числа на простоту (Prolog)

      Комментарии к записи Проверка числа на простоту (Prolog) отключены

Помечено: ,

В этой теме 2 ответа, 2 участника, последнее обновление  Васильев Владимир Сергеевич 8 мес. назад.

  • Автор
    Сообщения
  • #2875

    questioner
    Участник

    Нужно написать на языке Prolog программу проверки числа на простоту. У меня есть этот код для Visual Prolog:

    predicates
      simple(integer,integer)
      simple1(integer)
    clauses
      simple(X,I):-
        X mod I=0,!.
      simple(X,I):-
        I*I<=X,I1=I+1,
        simple(X,I1).
      simple1(1):-!.
      simple1(2):-!.
      simple1(X):-
        not(simple(X,2)).

    Я не понимаю что тут происходит. Помогите разобраться.

  • #2876

    Первое правило предиката simple у вас проверяет что число X делится на I без остатка. Если первое правило не сработает, то второе инициирует рекурсивную проверку с числом I+1. Перебор чисел продолжится до тех пор, пока X не станет больше I*I. Квадрат тут используется потому, что достаточно проверить делители от двойки до корня квадратного из числа.

    Предикат simple1 завершается удачей если его аргумент – единица или двойка, или если simple для этого аргумента завершится неудачей.

  • #2877

    Более правильно ваш код переписать следующим образом:

    isDivisible(Number, Divisor):-
      Number mod Divisor = 0, !.
    isDivisible(Number, Divisor):-
      Divisor * Divisor <= Number,
      NextDivisor = Divisor + 1,
      isDivisible(Number, NextDivisor).
    
    isPrime(1):-!.
    isPrime(Number):-
      Number > 0,
      not(isDivisible(Number, 2)).

    Функция isDivisible проверяет что число Number делится на одно из чисел из диапазона [Divisor, Number^(1/2)]. А функция isPrime проверяет частный случай с числом равным единице и в случае если аргумент больше нуля – проверяет, что он не имеет делителей начиная с числа 2. Простые числа всегда положительные и если не выполнить сравнение с нулем – то в вашем случае получился бы вечный цикл.

Для ответа в этой теме необходимо авторизоваться.