Testing time complexity of different primality tests

primaility.hs

module Main where

import Criterion.Main

-- We're going to use this constant as a known prime to test our functions with.
testPrime :: Int
testPrime = 16127

-- And a known non-prime as well.
testNonPrime :: Int
testNonPrime = testPrime + 1

-- Naive approach to testing primality. Goes though each number [2..n-1] testing for factors. O(n).
isPrime1 :: Integral a => a -> Bool
isPrime1 p = all ((0/=) . mod p) [2..p-1]

-- Same as naive approach but only testing odd numbers. O(n/2)
isPrime2 :: Integral a => a -> Bool
isPrime2 p
    | even p = p == 2
    | otherwise = all ((0/=) . mod p) $ 2:[3,5..p-1]

-- Less naive. Reduces search space to [2..sqrt(n)]. O(sqrt(n)).
isPrime3 :: Integral a => a -> Bool
isPrime3 p = all ((0/=) . mod p) [2..top]
    where
        top = floor $ sqrt $ fromIntegral p

-- Same as above but only testing odd numbers. O(sqrt(n)/2)
isPrime4 :: Integral a => a -> Bool
isPrime4 p
    | even p = p == 2
    | otherwise = all ((0/=) . mod p) $ 2:[3,5..top]
    where
        top = floor $ sqrt $ fromIntegral p

-- Constant time approach using Fermat's little theorem. O(1)
isPrime5 :: Integral a => a -> Bool
isPrime5 p = (2^(p-1)) `mod` p == 1

-- Benchmarking program.
main :: IO ()
main = defaultMain
    [bgroup "isPrime"
        [bench "1" $ nf (\n -> isPrime1 n :: Bool) testPrime
        ,bench "2" $ nf (\n -> isPrime2 n :: Bool) testPrime
        ,bench "3" $ nf (\n -> isPrime3 n :: Bool) testPrime
        ,bench "4" $ nf (\n -> isPrime4 n :: Bool) testPrime
        ,bench "5" $ nf (\n -> isPrime5 n :: Bool) testPrime
        ]
    ,bgroup "isntPrime"
        [bench "1" $ nf (\n -> isPrime1 n :: Bool) testNonPrime
        ,bench "2" $ nf (\n -> isPrime2 n :: Bool) testNonPrime
        ,bench "3" $ nf (\n -> isPrime3 n :: Bool) testNonPrime
        ,bench "4" $ nf (\n -> isPrime4 n :: Bool) testNonPrime
        ,bench "5" $ nf (\n -> isPrime5 n :: Bool) testNonPrime
        ]
    ]

primality.py

from math import sqrt, floor

# We're going to use this constant as a known prime to test our functions with.
testPrime = 16127

# And a known non-prime as well.
testNonPrime = testPrime + 1

# Naive approach to testing primality. Goes though each number [2..n-1] testing for factors. O(n).
def isPrime1 (p):
    for x in range(2,p):
        if p % x == 0:
            return False
    return True

# Same as naive approach but only testing odd numbers. O(n/2)
def isPrime2 (p):
    if p % 2 == 0:
        return False
    else:
        for x in range(3,p,2):
            if p % x == 0:
                return False
        return True

# Less naive. Reduces search space to [2..sqrt(n)]. O(sqrt(n)).
def isPrime3 (p):
    upper = int(floor(sqrt(p)))
    for x in range(2,upper):
        if p % x == 0:
            return False
    return True

# Same as above but only testing odd numbers. O(sqrt(n)/2)
def isPrime4 (p):
    if p % 2 == 0:
        return False
    else:
        upper = int(floor(sqrt(p)))
        for x in range(3,upper,2):
            if p % x == 0:
                return False
        return True

# Constant time approach using Fermat's little theorem. O(1)
def isPrime5 (p):
    return (2**(p-1)) % p == 1