How the Klong Primality Test Works

{&/x!:\2+!_x^1%2}

The braces around an expression denote a function. Because this function contains a single variable, x, it is a monadic function or a monad. When typing in the above code at the Klong prompt, the interpreter will respond :monad.

You can apply the function to a value, say 251, using the Apply (@) verb, e.g.:

{&/x!:\2+!_x^1%2}@251

Expressions evaluate from the right to the left, so the first thing the function does is 1 Divide 2, giving 0.5:

{&/x!:\2+!_x^1%2}@251

The next operation is x Power (1 Divide 2). x^1/2 is the square root of x, so this part of the expression computes the square root of 251:

{&/x!:\2+!_x^1%2}@251

Floor (_) then floors (rounds toward –infinity) that value. So _x^1%2 is Floor (x Power (1 Divide 2)), in this case the floor of the square root of 251.

{&/x!:\2+!_x^1%2}@251

Enumerate (!) creates a vector containing all integers from zero up to, but not including, that value. In this case, !_251^1%2 = !_15.84... = !15 = [0 ... 14] (a vector of the numbers from 0 to 14).

{&/x!:\2+!_x^1%2}@251

A number plus a vector gives a new vector with the number added to each of its elements, so 2+ adds 2 to each element from the previous step: 2+[0 ... 14] = [2 ... 16].

{&/x!:\2+!_x^1%2}@251

!:\ is a combination of the verb ! (Remainder) and the adverb :\ (Each-Left). x Remainder-Each-Left applies Remainder to each element of the previous step (v) with x as its left operand. It creates a new vector containing (x!v0),(x!v1),..., i.e.: (251!2),(251!3),(251!4),(251!5)... = (1),(2),(3),(1),... = [1 2 3 1 ...].

{&/x!:\2+!_x^1%2}@251

&/ is a combination of Min and Over. Min returns the minimum of two numbers and Over folds Min over a vector, so Min-Over returns the minimum of a vector:

{&/x!:\2+!_x^1%2}@251

In this case, the minimum of the vector is 1, because 1 is the smallest remainder obtained by dividing 251 by 2..16. In other words, 251 is prime.

If we had applied the function to a non-prime number, like 253, at least one of the elements of the vector would have divided that number with a remainder of 0, so the result of the function would also be 0.

{&/x!:\2+!_x^1%2}@253

Of course, the prime function is sufficiently complex to bind it to a name using Define (::):

prime::{&/x!:\2+!_x^1%2}

You can then use the function application syntax to apply it to some values:

prime::{&/x!:\2+!_x^1%2}
prime(251)
prime(253)

Of course, the @ operator would also work:

prime@251

BTW, the prime function only works for values greater than two. What will it return for 0, 1, and 2? Why?