A Prime Number can be divided evenly only by 1, or itself. And it must be a whole number greater than 1.

A simple method would be to iterate over numbers 2 to N, checking if it was divisible by all natural numbers greater than 2, and below the current value.

Once checked that it is not divisible by 2 there is not point checking for 4, 6, 8 etc. Remembering the definition of prime all numbers that are not prime are integer multiples of prime. so we have reduced the amount of work involved in testing primality.

parameter        N        = 1000;          
reg       [31:0] prime_number [0:N-1]; Store 0 to N prime numbers
integer          test     ; // Result of primality test
integer          k        ; // Currently looking for k'th prime 
integer          index    ; // Counts 1 to k, indexing previous primes 
integer          number_ut; // Number Under test

reg        [1:0] state   ; 
localparam       S_INC   = 2'b01;
localparam       S_CHECK = 2'b10;

initial begin
  prime_number[0] = 'd2; //Preload first Prime
  state           = S_CHECK; //Check set count first
  number_ut       = 'd3; // Number Under Test
  k               = 'd1; // Position 0 preloaded
  index           = 'd0;
  test            = 'd1;
end

always @(posedge clk ) begin
  if (state == S_INC) begin
    number_ut <= number_ut+1 ;
    state     <= S_CHECK ;
    index     <= 'd0;
    test      <= 'd1; // Safe default
  end
  else if (state == S_CHECK) begin
    if (test == 0) begin
      // Failed Prime test (exact divisor found)
      $display("Reject %3d", number_ut);
      state           <= S_INC ;
    end
    else if (index == k) begin
      //Passed Prime check
      //Use k+1 so that 2 is number 1, 3 is 2nd etc
      $display("Found the %1d th Prime, it is %1d", k+1, number_ut);
      prime_number[k] <= number_ut;
      k               <= k + 1;
      state           <= S_INC ;
    end
    else begin
      test  <= number_ut % prime_number[index] ;
      index <= index + 1;          
    end
  end
end

This is however just a programming exercise as the resulting hardware is likely substantially bigger than just implementing a look up table to the maxim number of primes you can fit in prime_number. The look up table will also be ready from time zero and not need to recompute every time you power up.

"Algebra : Properties of Real (ℝ) Numbers"

Commutative

Configurable order of numbers:

x+y = y+x
xy  = yx

Associative

Order that multiplication is applied :

(x+y)+z …

"matrix: A Ruby Standard Library"

Originally written as an assignment for Ruby Mendicant University.

matrix is part of the Ruby Standard Library

Usage

A note …

Lizard-Spock

Other articles

"Algebra : Properties of Real (ℝ) Numbers"

Commutative

Associative

"matrix: A Ruby Standard Library"

Usage

Other articles

Commutative

Associative

Usage

social