🎉 Exercism Research is now launched. Help Exercism, help science and have some fun at research.exercism.io 🎉
Avatar of hyphenrf

hyphenrf's solution

to Prime Factors in the OCaml Track

Published at Jul 12 2020 · 0 comments
Instructions
Test suite
Solution

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.

Example

What are the prime factors of 60?

  • Our first divisor is 2. 2 goes into 60, leaving 30.
  • 2 goes into 30, leaving 15.
    • 2 doesn't go cleanly into 15. So let's move on to our next divisor, 3.
  • 3 goes cleanly into 15, leaving 5.
    • 3 does not go cleanly into 5. The next possible factor is 4.
    • 4 does not go cleanly into 5. The next possible factor is 5.
  • 5 does go cleanly into 5.
  • We're left only with 1, so now, we're done.

Our successful divisors in that computation represent the list of prime factors of 60: 2, 2, 3, and 5.

You can check this yourself:

  • 2 * 2 * 3 * 5
  • = 4 * 15
  • = 60
  • Success!

Getting Started

  1. Install the Exercism CLI.

  2. Install OCaml.

  3. For library documentation, follow Useful OCaml resources.

Running Tests

A Makefile is provided with a default target to compile your solution and run the tests. At the command line, type:

make

Submitting Incomplete Solutions

It's possible to submit an incomplete solution so you can see how others have completed the exercise.

Feedback, Issues, Pull Requests

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!

Source

The Prime Factors Kata by Uncle Bob http://butunclebob.com/ArticleS.UncleBob.ThePrimeFactorsKata

test.ml

(* 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

Community comments

Find this solution interesting? Ask the author a question to learn more.

What can you learn from this solution?

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.

  • What compromises have been made?
  • Are there new concepts here that you could read more about to improve your understanding?