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
Raw view Test code New version

More information

Link:http://fssnip.net/8O
Posted:13 years ago
Author:Arjen Kopinga
Tags: algorithms , primes , factorize , fold

This web site is created using F# and Suave web server. It is hosted on Azure and the source code is on GitHub. Contributions are welcome!

The first version of fssnip.net has been created by @tomaspetricek back in 2010. This web site is a new, open-source and contribution-friendly version.