1
$\begingroup$

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.

$\endgroup$

2 Answers 2

5
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ What you mean with implement them as table? You mean If I have 8-bit input I must manually assign prime number for all possibility from 0 until 255. Then the circuit is not extendable like full-adder circuit with just copying the previous logic cell $\endgroup$ Jun 11, 2022 at 15:41
  • $\begingroup$ @MuhammadIkhwanPerwira: the three solutions I mentioned are easily extendable, keeping the same structure, but of course you need to precompute a table of primes. $\endgroup$
    – user16034
    Jun 14, 2022 at 17:26
  • $\begingroup$ @MuhammadIkhwanPerwira: for general numbers, I don't know better methods than algorithmic ones, which are essentially sequential. $\endgroup$
    – user16034
    Jun 14, 2022 at 17:29
2
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.