Clock based 8 bit prime number detector

Question

I am developing a 8 bit unsigned prime number detector in VHDL, synthesizable, for a project.The objective is to do not only avoiding to use any sort of loops or latches as well as restricting it to only the FPGA 50Mhz clock.

We tried a clock-based using successive divisions but such implementation does not meet the timing requirements in Quartus Timequest when we try to output the result. When we comment the output it seems to work just fine, and we don't fully understand the why.

library ieee;
use ieee.std_logic_1164.all;
use ieee.numeric_std.all;

entity primeChecker is
    generic(NumCyclesWait :integer := 1000);
    port(   clock: in  std_logic;
            enable: in  std_logic;
            reset   : in  std_logic;
            input   : in std_logic_vector(7 downto 0);
            output  : out std_logic_vector(7 downto 0);
            isPrime   : out std_logic_vector(0 downto 0));
end primeChecker;

architecture arch of primeChecker is

    signal count: integer := 0;
    signal numToCheck : integer := 0;
    signal prime, primeOut : integer := 1;
    signal s_out: unsigned(7 downto 0);
    signal div : integer := 2;
    signal clockCount : unsigned(0 downto 0) := "0";

begin

    numToCheck <= to_integer(unsigned(input));

    process(clock)
    begin
        if(rising_edge(clock)) then
                if(count = NumCyclesWait) then

                    if ((numToCheck = 1) OR (numToCheck = 0)) then

                        prime <= 0;     --Not Prime

                    elsif(numToCheck > 2 and prime =1 and div < numToCheck) then
                            if (numToCheck rem div = 0) then
                                -- if the number is divisible
                                prime <= 0; 
                            end if;
                            div <= div +1;

                    end if;
                else

                    count <= count +1;

                end if;

                if(enable = '1') then
                    s_out <= to_unsigned(numToCheck,8);
                    count <= 0;
                    div <= 2;
                    primeOut <= prime;
                    prime <= 1;
                else
                    s_out <= s_out;
                end if;
        end if;



    end process;



    isPrime <= std_logic_vector(to_unsigned(primeOut,1));
    output <= std_logic_vector(s_out);

end arch ; -- arch

I expect for it not to trigger the "Timing requirement not met" error and for it to fully compile.

Answer 1

For fastest constant time response, I would take a different approach. Your task is to deal with eight bit numbers only and your FPGA probably has more than enough RAM to set up an 8-bit prime number lookup table where each table entry just indicates whether its index is a prime number or not:

type prime_numbers_type is array(0 to 255) of std_ulogic;
constant prime_numbers    : prime_numbers_type :=
                            ( '0', '0', '1', '1', '0', '1', ... );

This makes the vital part of your prime number detector overly simple:

is_prime <= prime_numbers(to_integer(unsigned(num_to_check)));

I would probably just write a small Tcl script to set up the lookup table.