4) An Example: Primality Testing

An Example: Primality Testing

Now that we have seen the basics of Brachylog, let's analyze a simple Brachylog program which solves a famous problem: testing whether or not a number is prime.

Here is a Brachylog program which tests the primality of its Input:

2∨1<I<?¬(;I≜%0)

Let's decompose this piece of code:

2           If the Input can be unified with 2, then obviously the Input is Prime
∨           OR
1<I<?       Let I be an integer strictly between 1 and the Input.
¬(          Check that what is inside the parentheses cannot be true
   ;I≜%0    True if the remainder of the Input divided by a specific value of I is 0
 )

For the record, the following (much shorter) program will also test the primality of its Input:

ḋl1

which works as such:

ḋ     Unify an implicit variable with the list of prime factors of the Input
 l1   True if the length of that implicit variable is 1

The shortest program to test primality is the following:

ṗ

ṗ is a built-in predicate which constrains its Input = Output to be a prime number. If its Input is ground, it will obviously only succeed if the Input is a prime number.