Compute the prime factors of a given natural number.
A prime number is only evenly divisible by itself and 1.
Note that 1 is not a prime number.
What are the prime factors of 60?
Our successful divisors in that computation represent the list of prime factors of 60: 2, 2, 3, and 5.
You can check this yourself:
For library documentation, follow Useful OCaml resources.
A Makefile
is provided with a default target to compile your solution and run the tests. At the command line, type:
make
It's possible to submit an incomplete solution so you can see how others have completed the exercise.
The exercism/ocaml repository on GitHub is the home for all of the Ocaml exercises.
If you have feedback about an exercise, or want to help implementing a new one, head over there and create an issue or submit a PR. We welcome new contributors!
The Prime Factors Kata by Uncle Bob http://butunclebob.com/ArticleS.UncleBob.ThePrimeFactorsKata
(* prime-factors - 1.1.0 *)
open Base
open OUnit2
open Prime_factors
(* Assert Equals *)
let ae exp got _test_ctxt =
let printer xs = List.map xs ~f:Int64.to_string |> String.concat ~sep:";" in
assert_equal exp got ~printer
let to_int64s = List.map ~f:Int64.of_int
(* 64 bits integers are needed for the last number.
*
* If you happen to use a 64 bits machine normal ints would do as well, but this
* works for everybody.
*)
let tests = [
"no factors" >::
ae (to_int64s []) (factors_of 1L);
"prime number" >::
ae (to_int64s [2]) (factors_of 2L);
"square of a prime" >::
ae (to_int64s [3; 3]) (factors_of 9L);
"cube of a prime" >::
ae (to_int64s [2; 2; 2]) (factors_of 8L);
"product of primes and non-primes" >::
ae (to_int64s [2; 2; 3]) (factors_of 12L);
"product of primes" >::
ae (to_int64s [5; 17; 23; 461]) (factors_of 901255L);
"factors include a large prime" >::
ae (to_int64s [11; 9539; 894119]) (factors_of 93819012551L);
]
let () =
run_test_tt_main ("prime-factors tests" >::: tests)
module L = Int64
let factors_of n =
let rec factorise ?(fact=2L) ?(facts=[]) = function
| 1L -> List.rev facts
| i when L.rem i fact = 0L ->
factorise ~fact:fact ~facts:(fact::facts) (L.div i fact)
| i -> factorise ~fact:(L.add fact 1L) ~facts:facts i
in factorise n
A huge amount can be learned from reading other peopleâ€™s code. This is why we wanted to give exercism users the option of making their solutions public.
Here are some questions to help you reflect on this solution and learn the most from it.
Level up your programming skills with 3,429 exercises across 52 languages, and insightful discussion with our volunteer team of welcoming mentors. Exercism is 100% free forever.
Sign up Learn More
Community comments