Prime factorization in haskell

Tagged as haskell, algorithm

Written on 2013-10-26 16:09:32

While working on some lecture code, I came across the problem of factorization of integers. Since there is no trivial approach to this (to handle this for big values), cryptography works at all. I wondered if there was some way of doing this with list comprehensions in haskell, but my math skills are not adequate it seems. Or it is just not possible. ;o)

This was my shot of doing it in haskell, although without list comprehensions. (It may work with list comprehensions and helper functions, but I did not dig into this any further.)

 1      -- prime factorization
 2      priming :: Int -> [Int]
 3      priming x = primingh 2 x []
 4  
 5      -- helper function for tail recursion
 6      primingh :: Int -> Int -> [Int] -> [Int]
 7      primingh c x xs | (c == x) = reverse(x:xs)
 8                      | x == 1 = reverse(xs)
 9                      | ((mod x c) == 0) = (primingh c (div x c) (c:xs))
10                      | otherwise = (primingh (c+1) x xs)

Lines 7 and 8 are the terminal conditions, 9 handles existing double primes. (In case your value can be divided several times by the currently tested number, i.e. '2' without remainder.) The reverse just reverses the output list, so it lists increasing instead of decreasing result primes.

Note to self:
Haskell is not a Lisp. Do not name helper functions <functionname>-h, it will not recognize the '-'...


Unless otherwise credited all material Creative Commons License by sjas