 2 people like it.

# Folding over prime factors

Let's have some fun with higher order functions and instead of folding over a list, fold over the prime factors of a number. It can be optimized further by dividing out real primes instead of numbers of the form 6k+/-1, but it's not embarrassingly slow.

 ``` 1: 2: 3: 4: 5: 6: 7: 8: 9: 10: 11: 12: 13: 14: 15: 16: 17: 18: 19: 20: 21: 22: 23: 24: 25: 26: ``` ``````// A higher order variant of factorize, folding over prime factors of n // f: state -> factor -> state let factorf f state n = // Yields numbers of the form 6k +/- 1 (and 3) let inline next n = match n with | 2L -> 3L | 3L -> 5L | n -> if n % 6L = 5L then n + 2L else n + 4L let rec aux state p n = if p = n then f state p elif p * p > n then f state n elif n % p = 0L then aux (f state p) p (n / p) else aux state (next p) n aux state 2L n // Factorize a number: fold each prime factor into a list let factorize = factorf (fun acc p -> p::acc) [] // The product of prime factors of n better be equal to n let sanitycheck n = factorf (*) 1L n = n // A square-free number contains no repeating prime factors let squarefree = factorf (fun (flag,prev) p -> (flag && p <> prev, p)) (true,0L) >> fst ``````
val factorf : f:('a -> int64 -> 'a) -> state:'a -> n:int64 -> 'a

Full name: Script.factorf
val f : ('a -> int64 -> 'a)
val state : 'a
val n : int64
val next : (int64 -> int64)
val aux : ('a -> int64 -> int64 -> 'a)
val p : int64
val factorize : (int64 -> int64 list)

Full name: Script.factorize
val acc : int64 list
val sanitycheck : n:int64 -> bool

Full name: Script.sanitycheck
val squarefree : (int64 -> bool)

Full name: Script.squarefree
val flag : bool
val prev : int64
val fst : tuple:('T1 * 'T2) -> 'T1

Full name: Microsoft.FSharp.Core.Operators.fst