Classic Problem · A common assignment, solved and verified

4-Bit Prime Number Detector

Build a circuit that outputs 1 if a 4-bit binary number (0-15) is prime. It's a common digital logic assignment specifically because the primes don't fall into an obvious pattern the way "even numbers" or "multiples of 4" would — it genuinely tests whether you can group correctly.

The problem

The primes between 0 and 15 are 2, 3, 5, 7, 11, and 13. (1 isn't considered prime, and 0 obviously isn't.) That's six required 1s scattered across sixteen possible inputs, with no repeating bit pattern to lean on the way there would be for, say, "is this number even."

Value	Binary	Prime?
0	0000	0
1	0001	0
2	0010	1
3	0011	1
4	0100	0
5	0101	1
6	0110	0
7	0111	1
8-10, 12, 14, 15	—	0
11	1011	1
13	1101	1

The minimization

Grouped and verified against the solver:

F = A′B′C + B′CD + BC′D + A′CD

Four overlapping 2-cell groups, each picking up part of the scattered prime set. Notice every term includes C — every prime in this range except 2 is odd, and even 2 (0010) still has its C bit set, so C=1 turns out to be a necessary condition across the entire required set, which is why it appears in every single term.

Input

Variables

Karnaugh Map

Minimal Result

Output format

F = 0

Prime Implicant Analysis

Auto-generated Circuit

Universal Gate Conversion

Frequently asked questions

Should 1 be treated as prime in this problem?

No — 1 is excluded from the standard definition of a prime number, and this solution treats it as such (minterm 1 is 0, not 1). Some assignment variations do it differently, so check what your specific problem asks for.

Why doesn't this simplify to something with fewer literals?

Primes don't correspond to any single bit pattern — there's no shortcut like "look at just one or two bits." Four terms, all essential, is the genuine minimum for this exact set.

Would extending this to 5 or 6 bits (larger prime ranges) work the same way?

The same process applies, but primes get sparser as the range grows, typically needing more terms rather than fewer — try it on the 5-variable solver with primes up to 31.