patternMinor

Functionaly Finding Prime Factors with Multiplicity

Submitted by: @import:stackexchange-codereview·Mar 10, 2026·

Viewed 0 times

factorsfunctionalywithfindingprimemultiplicity

Problem

I am quite new to Haskell so any suggestions are welcome, also I noticed that it works quite slow even for something like

prime_factors_mult (2*2*2*2*3*3*3*5*5*7*7*7*7*13*13*13*17*19)

Also I may not know of coding conventions/formatting styles and better ways to do things,so you may also help me with that:

prime_factors_mult :: Int -> [(Int, Int)]
prime_factors_mult n =
    reverse . fst $
        foldl
            (\acc@(factors, val) x
                -> if val `mod` x == 0 then
                    let (k, v) = reduce val x in ((x, k) : factors, val `div` v)
                else
                    acc
            )
        ([], n)
        [2 .. floor . sqrt . fromIntegral $ n]

reduce :: Int -> Int -> (Int, Int)
reduce val x =
    if val `mod` x == 0 then
        let (k, v) = reduce (val `div` x) x in (1 + k, v * x)
    else
        (0, 1)

Solution

First of all, we can make your prime_factors_mult easier to read if we use where:

prime_factors_mult :: Int -> [(Int, Int)]
prime_factors_mult n = reverse . fst . foldl go ([], n) $ candidates
  where
    candidates = [2 .. floor . sqrt . fromIntegral $ n]
    go acc@(factors, val) x 
      | val `mod` x == 0 = let (k, v) = reduce val x in ((x, k) : factors, val `div` v)
      | otherwise        = acc

By the way, Haskell programs use camelCase, so primFactorsMult would be appropriate. However, does this function really capture your intend? Let us write it as imperative variant for a second:

# pseudo-python
def prime_factors_mult(n):
    result = []

    for i in range(2, sqrt(n)):
        count = 0
        while n % i == 0:
            n = n / i
            count = count + 1

        if count > 0:
            result = result.append({i, count})

    return result

This is a lot easier to read. We should strive to have an algorithm in Haskell that's just as easy to read, right? By the way, both the pseudo-code as well as your original code contained an error: what happens on 2*7? \$\sqrt{14}

In most go functions we can stop much, much sooner if n is a prime if we know the original n. Why? (Hint: what is the largest prime factor that can be in a number? And what is the second largest prime factor?)

Code Snippets

prime_factors_mult :: Int -> [(Int, Int)]
prime_factors_mult n = reverse . fst . foldl go ([], n) $ candidates
  where
    candidates = [2 .. floor . sqrt . fromIntegral $ n]
    go acc@(factors, val) x 
      | val `mod` x == 0 = let (k, v) = reduce val x in ((x, k) : factors, val `div` v)
      | otherwise        = acc

# pseudo-python
def prime_factors_mult(n):
    result = []

    for i in range(2, sqrt(n)):
        count = 0
        while n % i == 0:
            n = n / i
            count = count + 1

        if count > 0:
            result = result.append({i, count})

    # n is prime at this point:
    if n > 1:
        result = result.append({n, 1})

    return result

isDivisibleBy n k = n `rem` k == 0

primeFactorsMult :: Int -> [(Int, Int)]
primeFactorsMult = go 2 
  where
    go _ 1 = []
    go k n 
       | n `isDivisibleBy ` k = (k, m)   : go (k + 1) (n `div` d)
       | n < k * k            = [(n, 1)]
       | otherwise            = go (k + 1) n
      where
        (m, d) = reduce n k

primeFactorsMult :: Int -> [(Int, Int)]
primeFactorsMult = filter ((0 /=) . snd) . go 2 
  where
    go _ 1 = []
    go k n 
       | n <= k    = [(n, 1)]
       | otherwise = (k, m)   : go (k + 1) (n `div` d)
      where
        (m, n') = reduce n k

primeFactorsMult :: Int -> [(Int, Int)]
primeFactorsMult n = filter ((0 /=) . snd) . snd . mapAccumL go n $ 2 : [3,5..n] 
  where
    go n k = (n `div` d, (k, m))
      where
        (m, n') = reduce n k

Context

StackExchange Code Review Q#162708, answer score: 3

Revisions (0)

No revisions yet.