Skip to content

Instantly share code, notes, and snippets.

@ddosia
Created January 6, 2015 12:11
Show Gist options
  • Save ddosia/ed5da98f1a70e094515c to your computer and use it in GitHub Desktop.
Save ddosia/ed5da98f1a70e094515c to your computer and use it in GitHub Desktop.
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))
@ddosia
Copy link
Author

ddosia commented Jan 6, 2015

prime_factors.byte took 1_410.68s (~23.5 minutes)

@ddosia
Copy link
Author

ddosia commented Jan 6, 2015

Rewrote in a straight way, so much less code and incredibly fast:

open Core.Std
open Int64

let rec factorize n = function
  | k when k > n -> []
  | k when n % k = 0L -> k :: (factorize (n / k) k)
  | k -> factorize n (k + 1L)

let factors_of k =
  factorize k 2L

factors_of 93819012550L -> Time: 24.9071ms

@seriyps
Copy link

seriyps commented Jan 6, 2015

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);
}

@ddosia
Copy link
Author

ddosia commented Jan 6, 2015

-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!

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment