Testing for Primes by Trial Division

The idea

A prime number has exactly two positive divisors, 1 and itself. The simplest test is trial division: try dividing the number n by 2, 3, 4 and so on, and see whether any of them divides it evenly. If one does, n is composite. If none does, n is prime.

There is a neat way to arrange this for a language with limited branching. Look for the smallest divisor of n that is at least 2. Every number n of at least 2 has such a divisor, because n divides itself. If that smallest divisor equals n, then no smaller divisor exists and n is prime. If it is smaller, n is composite. That turns the problem into a single loop followed by a single comparison.

The program

The number being tested is 29, pushed as 3 × 9 + 2. This example value is prime.

39*2+09p2v                  +1<
         >:09g\%              |
                              0
                              9
                              g
                              -
         @,,,,,,,,,"composite"_"emirp",,,,,@

It prints prime. Replacing 39*2+ with 37* (21, which is 3 × 7) and padding with spaces prints composite.

Setup. 39*2+ computes 3 × 9 + 2 = 29. 09p stores it in the cell at column 0, row 9, so the loop can read n whenever needed. Then 2 pushes the first divisor, and v sends the pointer down.

Loop. The right arrow in row 1 starts the loop. With the divisor d on the stack:

1. : gives [d, d]
2. 09g reads n, giving [d, d, n]
3. \ swaps, giving [d, n, d]
4. % computes n mod d, giving [d, n mod d]

The vertical-if pops the remainder. If it is zero, d divides n and the pointer goes down column 30. If it is nonzero, the pointer goes up to the left arrow in row 0 and travels west, where 1 and + add 1 to d. The v at column 9 returns it to the loop.

Decision. Column 30 runs downward through 0, 9, g, -. This reads n and subtracts it from d. The result goes to the horizontal-if in row 6. If it is zero, d equals n, the pointer moves east, and the cells "emirp" push the letters. The five commas then pop them in reverse, printing prime. A nonzero result sends the pointer west, where the cells are laid out so that the pointer meets composite letter by letter in the right order and prints it.

For 29 the loop tries d = 2, 3, 4 and so on up to 29, which is 28 trial remainders. None of 2 through 28 divides 29, and 29 mod 29 = 0, so the loop exits with d = 29, the subtraction gives zero, and the output is prime. For 21, d = 3 gives a remainder of 0, so the exit comes immediately with d = 3, the subtraction gives −18, and the output is composite.

Why this works in a tiny language

The test needs only division with remainder, a way to branch on zero and a way to keep n somewhere. The grid supplies the last through grid variables. There is no comparison instruction in the main loop, because both tests are conditional branching on a value being zero. The loop is guaranteed to end for any n of at least 2, since d eventually reaches n and n mod n is 0. For other inputs the guarantee fails, as described below.

Limits

The program is a demonstration, not a good primality test.

• Wasted work. If n has a divisor other than 1 and n, it has one that is at most the square root of n. So the loop could stop once d times d exceeds n, and then declare n prime. For 29 that would mean trying only 2 to 5 instead of 2 to 29. Adding this check means multiplying and comparing on every pass, which uses another conditional branch and a longer loop body, but the savings are large for big numbers.
• Bad inputs. For n = 1 the loop never finds a divisor, because 1 mod d is 1 for every d of 2 or more, so it keeps counting upward without end. For n = 0 the first test gives remainder 0, then 2 − 0 is nonzero, and the program reports composite, which is a matter of convention rather than mathematics. These are the kind of arithmetic edge cases that need a guard before the loop.
• Number size. Large n may exceed the interpreter’s integer range, and a long loop is slow. Interpreter performance varies a lot, so timing numbers are not meaningful here.
• Layout. The decision column and the mirrored message take up much of the grid. A shorter output such as a single letter would shrink the program.

Even a correct trial division is far too slow for numbers with many digits. Serious primality testing uses other methods, which are beyond what a Befunge program is likely to do.

A note on termination

For n of at least 2, this loop is guaranteed to stop, which is unusual enough to mention. In general, deciding whether an arbitrary program stops is the halting problem, which no algorithm can solve for all programs. Specific loops like this one can still be shown to stop, because of a simple argument: the divisor rises by one each time and must reach n. Compare a classic puzzle such as the FizzBuzz puzzle, where the loop count is fixed in advance and no such argument is needed.