Return to Answer

n % k is computed using the 42-byte modulus algorithm from my divisibility test answer.

n % k is computed using the 42-byte modulus algorithm from my divisibility test answer.

How it works (WIP)

If n = 1,n - 1 = 0 and the while loop

If n - 1 is non-zero, we enter the loop that n = 1 skips. The loop achieves the following.

{ While the top of the active stack is non-zero:
 This isn't a "real" loop; the code that follows will be
 executed at most once.
 (
 (
 ({}) Pop and push n - 1.
 () Yield 1.
 ) Push n - 1 + 1 = n.
 <> Switch to the second stack. Yields 0.
 ) Push n + 0 = n.
 We now have n and k = n - 1 on the first stack, and n on
 the second one. The setup stage is complete and we start
 employing trial division to determine n's primality.
 { While the top of the second stack is non-zero:
 {} Pop n (first run) or the last modulus (subsequent runs),
 leaving the second stack empty.
 <> Switch to the first stack.
 (
 (
 {} Pop n from the first stack.
 <
 (
 (
 {} Pop k (initially n - 1) from the first stack.
 [()] Yield -1.
 ) Push k - 1 to the first stack.
 () Yield 1.
 <> Switch to the second stack.
 ) Push k - 1 + 1 = k on the second stack.
 > Yield 0.
 ) Push n + 0 = n on the second stack.
 <> Switch to the first stack.
 ) Push n on the first stack.
 <> Switch to the second stack, which contains n and k.
 The first stack contains n and k - 1, so it is ready for
 the next iteration.
 {({}[()]<({}[()]<({}())>)>{(<()>)}{})}{}{} Compute n % k.‡
 } Stop if n % k = 0.
} Ditto.

‡ The modulus is computed using the 42-byte algorithm from my divisibility test answer.

How it works

If n = 1 is zero, the while loop

If n - 1 is non-zero, we enter the loop that n = 1 skips. It isn't a "real" loop; the code is only executed once. It achieves the following.

{ While the top of the active stack is non-zero:
 (
 (
 ({}) Pop and push n - 1.
 () Yield 1.
 ) Push n - 1 + 1 = n.
 <> Switch to the second stack. Yields 0.
 ) Push n + 0 = n.
 We now have n and k = n - 1 on the first stack, and n on
 the second one. The setup stage is complete and we start
 employing trial division to determine n's primality.
 { While the top of the second stack is non-zero:
 {} Pop n (first run) or the last modulus (subsequent runs),
 leaving the second stack empty.
 <> Switch to the first stack.
 (
 (
 {} Pop n from the first stack.
 <
 (
 (
 {} Pop k (initially n - 1) from the first stack.
 [()] Yield -1.
 ) Push k - 1 to the first stack.
 () Yield 1.
 <> Switch to the second stack.
 ) Push k - 1 + 1 = k on the second stack.
 > Yield 0.
 ) Push n + 0 = n on the second stack.
 <> Switch to the first stack.
 ) Push n on the first stack.
 <> Switch to the second stack, which contains n and k.
 The first stack contains n and k - 1, so it is ready for
 the next iteration.
 {({}[()]<({}[()]<({}())>)>{(<()>)}{})}{}{} Compute and push n % k.
 } Stop if n % k = 0.
} Ditto.

n % k is computed using the 42-byte modulus algorithm from my divisibility test answer.

Finally, we interpret the results to determine n's primality.

<> Switch to the first stack, which contains n and k - 1, where k is the
 largest integer that is smaller than n and divides n evenly.
 If (and only if) n > 1 is prime, k = 1 and (thus) k - 1 = 0.
{ While the top of the first stack is non-zero:
 {} Pop it.
} This pops n if n is prime, n and k - 1 if n is composite.
(
 [] Yield the height h of the stack. h = 1 iff n is prime).
 {} Pop 0.
) Push h + 0 = h.

{ While the top of the active stack is non-zero:
 This isn't a "real" loop; the code that follows will be
 executed at most once.
 (
 (
 ({}) Pop and push n - 1.
 () Yield 1.
 ) Push n - 1 + 1 = n.
 <> Switch to the second stack. Yields 0.
 ) Push n + 0 = n.
 {
 {}
 <>
 (
 (
 {}
 <
 (
 (
 {}
 [()] x
 )
 ()
 <>
 )
 >
 )
 <>
 )
 <>
 {({}[()]<({}[()]<({}())>)>{(<()>)}{})}{}{}
 }
}

{ While the top of the active stack is non-zero:
 This isn't a "real" loop; the code that follows will be
 executed at most once.
 (
 (
 ({}) Pop and push n - 1.
 () Yield 1.
 ) Push n - 1 + 1 = n.
 <> Switch to the second stack. Yields 0.
 ) Push n + 0 = n.
 We now have n and k = n - 1 on the first stack, and n on
 the second one. The setup stage is complete and we start
 employing trial division to determine n's primality.
 { While the top of the second stack is non-zero:
 {} Pop n (first run) or the last modulus (subsequent runs),
 leaving the second stack empty.
 <> Switch to the first stack.
 (
 (
 {} Pop n from the first stack.
 <
 (
 (
 {} Pop k (initially n - 1) from the first stack.
 [()]  Yield -1.
 ) Push k - 1 to the first stack.
 () Yield 1.
 <> Switch to the second stack.
 ) Push k - 1 + 1 = k on the second stack.
 > Yield 0.
 ) Push n + 0 = n on the second stack.
 <> Switch to the first stack.
 ) Push n on the first stack.
 <> Switch to the second stack, which contains n and k.
 The first stack contains n and k - 1, so it is ready for
  the next iteration.
 {({}[()]<({}[()]<({}())>)>{(<()>)}{})}{}{} Compute n % k.‡
 } Stop if n % k = 0.
} Ditto.

‡ The modulus is computed using the 42-byte algorithm from my divisibility test answer .