Prime check

Here is a tiny proof, when doing primality test, why it is enough to check divisors only up to sqrt(n) instead of n:

Let n divide q.

If n < sqrt(q) < q
then n < sqrt(q) < q/n < q

q/n < q is trivial

sqrt(q) < q/n
1/sqrt(q) < 1/n

sqrt(q) > n

Alternatively

If sqrt(q) < n < q
then q/n < sqrt(q) < n < q

sqrt(q) < n
sqrt(q) > q/n

Implementation of the algorithm in Haskell:

primetest :: Int -> Bool
primetest x = primetest' x $ (ceiling.sqrt.fromIntegral) x
  where
  primetest' 1 _ = False
  primetest' x 1 = True
  primetest' x y = if x `mod` y == 0 then False else primetest' x (y - 1)

The part where I do (ceiling.sqrt.fromIntegral) may look magical, but what it does is:
1. Convert x from integer to something that sqrt accepts
2. Calculate the sqrt of it
3. Convert it back to integer