1

I am trying to understand solutions of exercises in order to prepare my logic programming exam and somehow I could not understand the logic of the code below.

Explanations in the question:

n is a prime number n > 1 and 1 < m < n n/m has a non-zero remainder.

Here is the code:

isPrime(X) :- help(X,X).

help(X,Y) :-
   Y > 2,
   LOW is Y-1,
   Z is X mod LOW,
   Z > 0,
   help(X,LOW).
help(X,2).

Could someone please explain the code for me.

3
  • Check out this solution that I coincidentally just posted
    – lefunction
    Jul 8, 2015 at 20:28
  • 1
    you can also type the command trace. then run your program, it will trace each step so you can follow along.
    – lefunction
    Jul 8, 2015 at 20:34
  • @lefunction i never heard and used trace before. I tried it. Thank you.1 ?- trace. true.[trace] 1 ?- isPrime(6). Call: (6) isPrime(6) ? creep Call: (7) help(6, 6) ? creep Call: (8) 6>2 ? creep Exit: (8) 6>2 ? creep Call: (8) _G1570 is 6+ -1 ? creep Exit: (8) 5 is 6+ -1 ? creep Call: (8) _G1573 is 6 mod 5 ? creep Exit: (8) 1 is 6 mod 5 ? creep Call: (8) 1>0 ? creep Exit: (8) 1>0 ? creep Call: (8) help(6, 5) ? creep Call: (9) 5>2 ? creep Exit: (9) 5>2 ? creep Call: (9) _G1576 is 5+ -1 ? creep Exit: (9) 4 is 5+ -1 ? creep ...
    – limonik
    Jul 8, 2015 at 20:52

2 Answers 2

2

This code is attempting to determine if X is a prime number, by doing the following:

let Y = X initially
1. Check to see if the number (Y) is greater than 2.
2. Assign a new variable (LOW) one-less than the starting number (Y-1)
3. If X mod LOW is greater than zero, then recurse with LOW as the new Y

Repeat this until X mod LOW is greater than zero and your mod is 1 (Y=2), then if I'm reading this (and remembering the formula) correctly, you should have X as a prime.

If at some point X mod LOW equals zero, then X is a non-prime.
Example:  X=6 (non-prime)
Y=6, LOW=5, Z = 6 mod 5 = 1 --> help(6,5)
Y=5, LOW=4, Z = 6 mod 4 = 2 --> help(6,4)
Y=4, LOW=3  Z = 6 mod 3 = 0  --> non prime because it's divisible by 3 in this case

Example: X=5 (prime)
Y=5, LOW=4, Z= 5 mod 4 = 1  --> help(5,4)
Y=4, LOW=3, Z= 5 mod 3 = 2  --> help(5,3)
Y=3, LOW=2  Z= 5 mod 2 = 3  --> help(5,2)
Y=2, --> once you get to this point, X is prime, because LOW=1, 
and any number mod 1 is greater than zero, and you can't "X mod 0".

Make sense? It's effectively iterating over numbers less than X to see if it divides equally (mod = 0).

3
  • Maybe (just to hammer home the point) mention that when A mod B = 0, the zero remainder means that A is exactly divisible by B and hence not prime since B is a factor of it? (for future readers in a hurry)
    – MartynA
    Jul 8, 2015 at 19:44
  • Updated a line, hopefully that point is clear.. thanks for the suggestion.
    – Tim S.
    Jul 8, 2015 at 20:58
  • Thanks. I'm sure other students will run into the same source as the Op and may be equally perplexed ...
    – MartynA
    Jul 8, 2015 at 21:03
0

OK. The definition of a prime number :

An integer n is prime if the following holds true:

  • N is greater than 1, and
  • N is divisible only by itself and 1.

Since every integer is (A) divisible by itself, and (B) divisible by 1, there is no real need to check that these conditions hold true. The real constraint that must be checked is this:

For a number n to be prime, the following constraints must be satisfied:

  • n must be greater than 1, and
  • No m must exist in the domain 1 > m < n such that n is divisible by m

Your help/2 predicate enforces that second constraint, by seeding its second argument with the test value, and decrementing it, looking for an m that divides n.

An easier way might be to write the test in a declarative manner and let Prolog figure it out for you:

is_prime(2).         % 2 is prime by definition.
is_prime(N) :-       % otherwise, N is prime if,
  N > 2 ,            % - N is greater than 2, and
  0 =\= N mod 2      % - and N is odd (no real need to check even numbers, eh?
  not_divisible(3,N) % - and N is not divisible any other odd number in the range 3 -- (N-1) 
  .

not_divisible(N,N) .  % if we've counted up to N, we're good.
not_divisible(M,N) :- % otherwise...
  M < N ,             % - if M is less than N, and
  0 =:= N mod M       % - and N is not divisible by M, then
  M1 is M-1 ,         % - decrement M, and
  not_divisible(M1,N) % - recurse down on the newly decremented M
  .                   %
1
  • 1
    The other answer seems to be a better explanation of the code the Op originally asked about.
    – MartynA
    Jul 8, 2015 at 20:44

Your Answer

Reminder: Answers generated by Artificial Intelligence tools are not allowed on Stack Overflow. Learn more

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.