prime_factors.ml

open Core.Std
open Int64

let find_factor nums k = List.find nums ~f:(fun n -> k % n = 0L)

let rec next_prime primes n =
  match find_factor primes n with
  | Some _ -> next_prime primes (n + 1L)
  | None -> n


(* `primes' - currently known primes *)
(* `nums' - if we exhausted all currently known `primes', there is no need to
   check it twice each time we generate new one *)
(* `last_known_p' - is used in generation of next prime, we may use last
   element of `primes' list instead, but this will require O(n) steps, that is
   why it is maintained separately *)
let rec factorize primes nums last_known_p = function
  | k when k < 1L -> assert false
  | 1L -> []
  | k ->
    match find_factor nums k with
    | Some p -> p :: (factorize primes nums last_known_p (k / p))
    | None ->
      let next_p = next_prime primes (last_known_p + 1L) in
      let primes' = List.append primes [next_p] in
      factorize primes' [next_p] next_p k


let factors_of k =
  factorize [2L] [2L] 2L k

let () =
  let start = Time.now () in
  let _ = factors_of 93819012551L in
  let stop = Time.now () in
  printf "Time: %s\n" (Time.Span.to_string (Time.diff stop start))

Rust version (imperative)

fn factorize(mut n: u64, mut k: u64) -> Vec<u64> {
    let mut vec = Vec::new();
    while k <= n {
        if n % k == 0 {
            vec.push(k);
            n = n / k;
        } else {
            k = k + 1;
        }
    }
    vec
}

fn factors_of(k: u64) -> Vec<u64> {
    factorize(k, 2)
}

fn main() {
    let k = 93819012551;
    let factors = factors_of(k);
    println!("Factors of {} are {}", k, factors);
}

-module(prime_factors).

-export([
   factorize/2
]).

factorize(N, K) when K > N ->
    [];
factorize(N, K) when N rem K == 0 ->
    [K | factorize(N div K, K)];
factorize(N, K) ->
    factorize(N, K + 1).

erl
Erlang R16B03 (erts-5.10.4) [source] [64-bit] [smp:4:4] [async-threads:10] [hipe] [kernel-poll:false]

1> timer:tc(prime_factors, factorize, [93819012551, 2]).
{61767,[11,9539,894119]}

not bad Erlang, not bad!