---
title: "Prime number checking processor"
subject: "Embedded System"
chapter: 2
key: "semester_6/embedded_system:spp-prime-check"
source: https://www.bctengineer.com/q/semester_6/embedded_system/spp-prime-check
site: BCT Engineering
---

# Prime number checking processor

Embedded System · Chapter 2: Hardware Design Issues

- Asked in: 2078 Poush, 8 marks
- Video: [Designing Single Purpose Processor To Calculate GCD (HCF).](https://www.youtube.com/watch?v=Wy344fMRnOo) — AFlick
- Answer checked by Claude Opus 5.5 (high effort) on 2026-10-14
- Page: https://www.bctengineer.com/q/semester_6/embedded_system/spp-prime-check
- Whole chapter: https://www.bctengineer.com/md/semester_6/embedded_system/chapter-2

## Question

Develop an algorithm, draw FSMD and design datapath of a custom single-purpose processor to generate 1 or 0 if the input integer is prime or not. Also show the block diagram of controller.

## Short answer

The algorithm checks n<2 (not prime), then iterates i from 2 to n-1, computing n mod i by repeated subtraction; if remainder zero, not prime. The datapath has registers N, I, R, subtractor, comparators; the controller is an 8-state FSM with status flags lt2, ige, rge, rz.

## Answer

**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
```text
 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
| State | Condition | Actions | Next |
|---|---|---|---|
| S0 wait | start = 0 | done = 0 | S0 |
| S0 | start = 1 | N = n | S1 |
| S1 | N < 2 | none | S7 |
| S1 | N >= 2 | I = 2 | S2 |
| S2 | I >= N | none | S6 |
| S2 | I < N | R = N | S3 |
| S3 | R >= I | none | S4 |
| S3 | R < I | none | S5 |
| S4 | always | R = R - I | S3 |
| S5 | R = 0 | none | S7 |
| S5 | R != 0 | I = I + 1 | S2 |
| S6 prime | always | P = 1, done = 1 | S0 |
| S7 not prime | always | P = 0, done = 1 | S0 |

```text
 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
```text
 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
```text
 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.

## Check yourself

The answer's key points as multiple-choice questions, with the correct option and why.

1. How is n mod i computed when there is no divider?
   A. Add i to R until it equals n
   B. Copy n into R and subtract i repeatedly while R >= i
   C. Multiply n by i
   D. Shift n right by i
   Answer: B. After repeated subtraction, R holds the remainder. (Key point: Mod without divider)

2. When is n declared not prime in the loop?
   A. When R is not zero
   B. When i equals n
   C. When the remainder R is 0 for some i < n
   D. When n >= 2
   Answer: C. A zero remainder means i divides n, so n is composite. (Key point: Not prime condition)

3. When is P set to 1?
   A. When n < 2
   B. When R = 0
   C. After the first loop
   D. When i reaches n without any zero remainder
   Answer: D. If no i from 2 to n-1 divides n, then n is prime (state S6). (Key point: Prime result)

4. Why is 9 reported as not prime?
   A. At i = 3, R goes 9, 6, 3, 0 so R = 0
   B. At i = 2, R = 0
   C. i reaches 9 with no zero remainder
   D. Because 9 < 2
   Answer: A. 9 mod 3 = 0, so S5 sends control to the not prime state with P = 0. (Key point: Trace n = 9)

## Related in Embedded System

- [Dual-purpose processor: factorial and prime](https://www.bctengineer.com/question.md?key=semester_6%2Fembedded_system%3Adual-purpose-factorial-prime) — Embedded System, chapter 2
- [Single-purpose processor for power](https://www.bctengineer.com/question.md?key=semester_6%2Fembedded_system%3Aspp-power) — Embedded System, chapter 2, asked 2×
- [Factorial single-purpose processor](https://www.bctengineer.com/question.md?key=semester_6%2Fembedded_system%3Aspp-factorial) — Embedded System, chapter 2
- [Fibonacci single-purpose processor](https://www.bctengineer.com/question.md?key=semester_6%2Fembedded_system%3Aspp-fibonacci) — Embedded System, chapter 2, asked 2×
- [Design LCM single-purpose processor](https://www.bctengineer.com/question.md?key=semester_6%2Fembedded_system%3Aspp-lcm-datapath-controller) — Embedded System, chapter 2
- [Largest of four integers processor](https://www.bctengineer.com/question.md?key=semester_6%2Fembedded_system%3Aspp-largest-of-four) — Embedded System, chapter 2

## Related in other subjects

- [DMA controller block diagram and transfer](https://www.bctengineer.com/question.md?key=semester_5%2Fcomputer_organization_and_architecture%3Adma-controller) — Computer Organization and Architecture, chapter 7, asked 6×
- [Algorithm for numbers divisible by 9 not 6](https://www.bctengineer.com/question.md?key=semester_1%2Fcomputer_programming%3Aalgo-flowchart-divisible-9-not-6) — Computer Programming, chapter 2
- [Derivative feedback controller: block diagram and effect](https://www.bctengineer.com/question.md?key=semester_3%2Fcontrol_systems%3Aderivative-feedback-bd-effect) — Control Systems, chapter 7, asked 2×
- [PID controller block diagram, transfer function, characteristics](https://www.bctengineer.com/question.md?key=semester_3%2Fcontrol_systems%3Apid-bd-tf-characteristics) — Control Systems, chapter 7