First, let’s define a function that finds factors using trial division:
tdFactors :: Integer -> [Integer] -> [Integer] tdFactors _  =  tdFactors r (x:xs) | x * x > r = [r] | mod r x == 0 = x : tdFactors (div r x) (x:xs) | otherwise = tdFactors r xs
Using that, the function for naive factorization is trivial:
factorNaive :: Integer -> [Integer] factorNaive n = tdFactors n [2..]
Now for the wheel factorization. First we define a function that tells us which columns of our wheel to use given the circumference.
spokes :: Integer -> [Bool] spokes c = map ((== 1) . gcd c) [1..c]
To construct our wheel, we keep repeating this pattern and use only the numbers from the correct columns (and correct the start of the wheel).
wheel :: [Integer] -> [Integer] wheel ps = (ps ++) . drop 1 . map snd . filter fst $ zip (cycle . spokes $ product ps) [1..]
The function to do wheel factorization is practically identical to the naive one:
factorWheel :: Integer -> [Integer] factorWheel n = tdFactors n $ wheel [2,3,5,7]
And of course we need to test if everything works:
main :: IO () main = do print $ factorNaive 600851475143 print $ factorWheel 600851475143
And we’re done. Pretty simple.