Combinational logic check if bits is prime

Question

I wonder if there's Digital Logic Circuit (using combinatorial logic gates) that check if number is prime or not.

For example given input fixed 8-bit that will produce 1-bit output.

00000101 will produce output 1 (1 means prime)

00000110 will produce output 0 (0 means composite).

I know it's possible if using Sequential Logic, well basically when you program to check if number is prime with high level program language such as Python is one of example Sequential Logic at cost of time.

While when using Combinational Logic, it's instantanously (not sure due to delay propagation from electricity) computed at cost of many logic gates will be used.

Answer 1

There is no known regularity in the primes, and for small numbers (such as 8 bits naturals), the best is to implement them as a table.

If you want an instant answer, one comparator per prime can do. Otherwise, binary search can be implemented in hardware, possibly storing a binary trie. Or simply an array of bits, one per integer.

Answer 2

Of course, the circuit will just grow rapidly. For 8 bits there is no problem.

You check whether bit 0 is 0 or 1. If it is 0, then you check whether the input is 2.

If it is 1, then you check bit 7. If bit 7 is set then n must be one of the primes from 67 to 127, otherwise it must be one of the primes from 3 to 61. In each case, you check bit 6, and n must be an odd prime in a range of 64 integers, and so on. For example in the branch with bits 00001xx1, there are two primes 11 and 13, so the remaining two bits must be 01 or 10.

For k bit input you will need roughly $2^k$ gates, and the delay should be roughly k gates.