Prime number checking processor

Assumption: input n is an 8-bit unsigned integer. Output P = 1 if n is prime, else 0. There is no divider, so "n mod i" is done by repeated subtraction.

Algorithm

 if (n < 2) P = 0
 else:
    i = 2
    while (i < n):
        r = n
        while (r >= i) r = r - i     // r = n mod i
        if (r == 0) { P = 0; stop }
        i = i + 1
    P = 1

FSMD

 S0 --start--> S1 --N>=2 (I=2)--> S2 --I<N (R=N)--> S3
 S1 --N<2--> S7                   S2 --I>=N--> S6
 S3 --R>=I--> S4 (R=R-I) --> S3   S3 --R<I--> S5
 S5 --R=0--> S7    S5 --R!=0 (I=I+1)--> S2
 S6, S7 (set P, done=1) --> S0

Datapath

 n -> [N] ---> [N<2], [I>=N] comparators ---> to controller
      [I] <- mux(2, I+1)        [ I+1 ] incrementer
      [R] <- mux(N, R-I)        [ R-I ] subtractor
      [R>=I] comparator, [R==0] detector --> to controller
      [P] output flag register (1/0)

Components: registers N, I, R, P; incrementer, subtractor; comparators (N<2, I>=N, R>=I), zero detector (R = 0); muxes for I (2 or I+1) and R (N or R-I). Status outputs: lt2, ige, rge, rz.

Controller block diagram

 start, status flags --> +-------------+   +-----------+
 (from datapath)         | Next-state  |-->| State     |
                         | logic       |   | register  |
                         +------^------+   +-----+-----+
                                |   current state |
                                +-----------------+
                                                  v
                                           +-------------+
                                           | Output logic|--> control
                                           +-------------+    signals

13 transitions over 8 states (3-bit binary encoding). Control signals: N_ld, I_sel/I_ld, R_sel/R_ld, P_set, P_clr, done.

Trace n = 7: I = 2: R = 7, 5, 3, 1 (R < 2, R != 0) -> I = 3 ... I = 7 = N -> P = 1. n = 9: I = 3, R = 9, 6, 3, 0 -> R = 0 -> P = 0.