To check if n is prime, test if any number from 2 to √n divides n. If none do, n is prime.
Why √n: if n has a divisor d > √n, then n/d < √n. You would have found n/d already.
function isPrime(n): if n < 2: return false for i from 2 to sqrt(n): if n % i == 0: return false return true