Created
January 6, 2015 12:11
-
-
Save ddosia/ed5da98f1a70e094515c to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| 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)) |
Author
ddosia
commented
Jan 6, 2015
prime_factors.byte took 1_410.68s (~23.5 minutes)
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 2Lfactors_of 93819012550L -> Time: 24.9071ms
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!
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment