Question

Express in pseudocode the trial division algorithm for determining whether an integer is prime.

Short answer

The input is an integer n greater than 1. We try dividing it by all integers from 2 to $\sqrt{n}$, and if we find one that leaves no remainder then we know that n is not prime.

Step-by-step solution

Step 1

The input is an integer n greater than 1. We try dividing it by all integers from 2 to $\sqrt{n}$, and if we find one that leaves no remainder then we know that n is not prime. The pseudocode below accomplishes this.

procedure $prime\_tester$ (n: integer greater than 1) $isprime$:= true d:= 2 while $isprime$and $d*d$< = n if n mod d = 0 then $isprime$:= false else d:= $d+1$return $isprime$