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

-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