For example, if the input is 825 the output expected is (0 1 2 0 1). What this means is: 0 two's, 1 three's, 2 five's, 0 seven's and 1 eleven.
Doing this imperatively was quite easy for me. Functional, not so much. Could you please guide me how to go about solving the above problem in a functional way?
Note: Fold/reduce ways will be preferred over explicit recursion. :)
EDIT:
I'd appreciate the direct Haskell/Clojure code instead of a vague description.
Define a function factor that does exactly two things:
factor with the result of dividing the input number by the found factor.You will have to add something to step 1 in case there are no factors (i.e. the number is prime).
You can add another parameter to this function to represent the vector form that your output requires. Start with an empty list, and every time you find a factor, call factor recursively with a new list updated to represent the new factor you just found.
Code in Ruby.
@arr = []
def factorize(n)
2.upto(n){|x| (@arr << x; factorize(n/x); return) if n%x == 0}
end
def is_prime(n)
return false if n <= 1
2.upto(Math.sqrt(n).to_i){|x| return false if n%x == 0}
true
end
factorize(245)
1.upto(@arr.max){|each_num| puts @arr.count(each_num) if is_prime(each_num)}
# OUTPUTS 0 0 1 2, meaning ONE 5s and TWO 7s
Here's how I factored it, not sure if its what you're looking for...
factor :: Integer -> [Integer]
factor x = (filter (isFactor x) [1 .. (div x 2)]) ++ [x]
where
isFactor num possibleFactor = mod num possibleFactor == 0
Here's a recursive solution in Python. Note, it needs a precomputed array of known primes <= sqrt(number).
def factor(number, primes):
def divide(num,prime):
if num%prime:
return 0
else:
return 1+divide(num/prime,prime)
if number==0 or len(primes)==0 or number<primes[0]:
return []
elif number%primes[0]:
return [0]+factor(number,primes[1:])
else:
times=divide(number,primes[0])
return [times]+factor(number/(primes[0]**times),primes[1:])
if __name__=='__main__':
print factor(825,[2,3,5,7,11,13,17])
Here's some Erlang code that does what you want.
I'm new to Erlang myself, so this probably isn't the BEST way to do it (in fact, I'd appreciate feedback from others).
-module(factor).
-export([factor/1]).
num_times_divides(A, B) ->
num_times_divides(A, B, 0, 1).
num_times_divides(A, B, Count, Power) ->
if
(A rem B) == 0 -> num_times_divides(A div B, B, Count + 1, Power * B);
true -> {Count, Power}
end.
factor(N) ->
factor(N, [], 2).
factor(1, Factor_List, _) ->
Factor_List;
factor(N, Factor_List, F) ->
{Count, Quotient} = num_times_divides(N, F),
factor(N div Quotient, [Count | Factor_List], F + 1).
I assume from your question you can produce a lazy list of primes. This is a direct clojure code, with recursion, though. It could also be made more efficient.
(defn div-times
"How many times can n divideded by d"
[n d]
(loop [n n
d d
times 0]
(if (= 0 (mod n d))
(recur (/ n d) d (inc times))
[n times])))
(defn factorize
[n]
(loop [n n
factors []
primes (primes)]
(if (<= (first primes) n)
(let [[n times] (div-times n (first primes))]
(recur n (conj factors times) (next primes)))
factors))))
Here is my own Haskell trial. I'm still a Haskell newbie myself (but not really a newbie as a functional programmer), hence there is probably many possible improvements. I could probably find some myself thinking harder, but it works as expected and I see no obvious algorithmic slowness.
The code includes a primes number generator as one was necessary for a complete answer. OP could have provided his one primes generator as he said he know how to do it, it would have avoided including it in answers.
I don't see much difference between what I wrote functionaly using Haskell and what I could have wrote iteratively. The main difficulty was probably the strange expected format of the result.
module Primes
where
isPrime :: Integer -> Bool
isPrime a = isPrimeHelper a primes
isPrimeHelper a (p:ps)
| p*p > a = True
| a `mod` p == 0 = False
| otherwise = isPrimeHelper a ps
-- List of prime numbers
primes :: [Integer]
primes = 2 : filter isPrime [3..]
countFactor x p
| x `mod` p == 0 = 1 + countFactor (x `div` p) p
| otherwise = 0
cleanFactor x p
| x `mod` p == 0 = cleanFactor (x `div` p) p
| otherwise = x
nbFactors x (p:ps)
| x == 1 = []
| x `mod` p == 0 = (countFactor x p) : (nbFactors (cleanFactor x p) ps)
| otherwise = 0 : (nbFactors x ps)
-- List of number of times each prime number divides x
-- (tricky because the result is supposed to put 0 for non dividers primes,
-- but only for those smaller than larger prime divider...)
factor :: Integer -> [Integer]
factor x = nbFactors x primes
Unit tests are included below. As I use TDD I had to write them anyway.
module Main
where
import Test.HUnit
import Primes
test1 = True ~=? (isPrime 2)
test2 = True ~=? (isPrime 3)
test3 = False ~=? (isPrime 4)
test4 = True ~=? (isPrime 5)
test5 = 2 ~=? (primes !! 0)
test6 = 7 ~=? (primes !! 3)
test7 = 2 ~=? (countFactor 825 5)
test8 = 0 ~=? (countFactor 825 17)
test9 = 33 ~=? (cleanFactor 825 5)
test10 = [0, 1, 2, 0, 1] ~=? (factor 825)
tests = TestList [ test1, test2, test3, test4,
test5, test6,
test7, test8, test9,
test10
]
main = do runTestTT tests
Below is a better version suggested by yatima2975 that needs less calls to mod and div (that can be quite costly whith large numbers).
module Primes
where
isPrime :: Integer -> Bool
isPrime = isPrimeHelper primes
isPrimeHelper (p:ps) a
| p*p > a = True
| a `mod` p == 0 = False
| otherwise = isPrimeHelper ps a
-- List of prime numbers
primes :: [Integer]
primes = 2 : filter isPrime [3..]
countClean = countCleanHelper 0
countCleanHelper e x p = case divMod x p of
(x',0) -> countCleanHelper (e+1) x' p
_ -> (e,x)
nbFactors _ 1 = []
nbFactors (p:ps) x = let (exponent, rest) = countClean x p
in exponent : nbFactors ps rest
-- List of number of times each prime number divides x
-- (tricky because the result is supposed to put 0 for non dividers primes,
-- but only for those smaller than larger prime divider...)
factor :: Integer -> [Integer]
factor = nbFactors primes
And the updated tests
module Main
where
import Test.HUnit
import Primes
test1 = True ~=? (isPrime 2)
test2 = True ~=? (isPrime 3)
test3 = False ~=? (isPrime 4)
test4 = True ~=? (isPrime 5)
test5 = 2 ~=? (primes !! 0)
test6 = 7 ~=? (primes !! 3)
test7 = (2,33) ~=? (countClean 825 5)
test8 = (0,825) ~=? (countClean 825 17)
test10 = [0, 1, 2, 0, 1] ~=? (factor 825)
tests = TestList [ test1, test2, test3, test4,
test5, test6,
test7, test8,
test10
]
main = do runTestTT tests
My take (in Scala):
object PrimeFactors {
// Generates infinite prime numbers' sequence using Eratosthenes' Seieve
lazy val primes = {
def sieve(s: Stream[Int]): Stream[Int] = s match {
case x #:: xs => x #:: sieve(xs.filter(_ % x != 0))
}
sieve(Stream from 2)
}
// Divides a by b until the division gives a non-integral number.
// Returns number of times division was carried out followed by the
// number obtained on final division.
// For example, dividex(45, 3) gives (2, 5).
def dividex(a: Double, b: Double) = {
val s = Stream.iterate(a)(_ / b)
val i = s.indexWhere(x => x.toInt != x) - 1
(i, s(i).toInt)
}
def factorsOf(n: Int) = {
def factors(i: Int, n: Int): List[Int] = {
val (freq, n0) = dividex(n, primes(i))
if(n0 > 1)
freq :: factors(i + 1, n0)
else
freq :: Nil
}
factors(0, n).mkString("(", " ", ")")
}
def main(args: Array[String]) {
val n = readInt()
println(factorsOf(n))
}
}
A Clojure solution that uses recursion to define a good abstraction
(defn map-state
"Return a lazy seq of the state machine f's output when given the input in
coll and a initial state. f must be defined so that (f state input) returns a
seq of the output and the next state."
[f initial coll]
(lazy-seq
(if (seq coll)
(let [[out state] (f initial (first coll))]
(cons out (map-state f state (next coll)))))))
(def primes [2 3 5 7 11 13 17 19])
(defn factor
"Return a seq of the exponents of the prime powers of n"
[n]
(letfn [(get-count [n prime]
(if (= n 1)
[:end 1]
(let [divs (iterate #(/ % prime) n)
[zeros rest] (split-with #(zero? (mod % prime)) divs)]
[(count zeros) (first rest)])))]
(take-while #(not= % :end) (map-state get-count n primes))))
How about:
(defn factors [n]
(if (= n 1) '()
(loop [i 2]
(if (= 0 (mod n i)) (cons i (factors (/ n i)))
(recur (inc i))))))
Use it like:
(factors 1000) -> (2 2 2 5 5 5)
A fully tail recursive version
(defn factors [n]
(loop [acc [] i 2 n n]
(cond (= n 1) acc
(= 0 (mod n i)) (recur (conj acc i), i , (/ n i) )
:else (recur acc , (inc i), n ))))
Try:
(factors 1000) -> [2 2 2 5 5 5]
Slightly more complicated than it needs to be, but goes much faster:
(defn factors [n]
(loop [acc '() i 2 n n]
(cond (= n 1) acc
(< n (* i i)) (cons n acc)
(= 0 (mod n i)) (recur (cons i acc) i (/ n i) )
:else (recur acc (inc i) n ))))
Try:
(time (factors 123456789012345678901234567890)) ;;7 msec
Haskell version that gives the actual factors, where primes is an infinite lazy list of primes:
primefactors :: Integer -> [Integer]
primefactors 1 = []
primefactors x = [factor] ++ (primefactors (x `quot` factor))
where factor = (head [n | n <- primes, (x `mod` n) == 0])
Usage:
*Main> primefactors 65535
[3,5,17,257]
a C# implementation
public void Test()
{
var factors = Factorize(825)
.GroupBy(x => x)
.ToDictionary(x => x.Key, x => x.Count());
var outputs = Primes()
.TakeWhile(x => x <= factors.Max(y => y.Key))
.Select(x => factors.ContainsKey(x) ? factors[x] : 0)
.Select(x => x.ToString())
.ToArray();
Console.WriteLine(String.Join(", ", outputs));
}
public IEnumerable<int> Factorize(int input)
{
int first = Primes()
.TakeWhile(x => x <= Math.Sqrt(input))
.FirstOrDefault(x => input % x == 0);
return first == 0
? new[] { input }
: new[] { first }.Concat(Factorize(input / first));
}
public IEnumerable<int> Primes()
{
var ints = Enumerable.Range(2, Int32.MaxValue - 1);
return ints.Where(x => !ints
.TakeWhile(y => y <= Math.Sqrt(x))
.Any(y => x % y == 0));
}
output:
0, 1, 2, 0, 1
A must shorter Haskell solution that uses unfoldr. The list of exponents is lazy and never has any trailing zeros. The list Data.Numbers.Primes.primes is built lazily and the space is not released, I think you can use (wheelSieve 6) instead of "primes" if this is a space leak for you.
import Data.Numbers.Primes -- cabal install primes
import Data.List(unfoldr)
countFactors n = unfoldr iter (n,primes) where
iter (x,p:ps) | x < p = Nothing
| otherwise = let countP y acc = case quotRem y p of
(y2,0) -> countP y2 $! succ acc
_ -> (acc,(y,ps))
in Just (countP x 0)
In Factor:
USING: assocs kernel math.primes math.primes.factors sequences ;
: count-factors ( n -- seq )
group-factors [ [ first ] map supremum primes-upto ] keep
[ at 0 or ] curry map ;
Demo:
825 count-factors .
V{ 0 1 2 0 1 }