In today’s Programming Praxis problem we’re supposed to factor numbers both the naive way and using Wheel factorization. Let’s go.

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.