ðŸŽ‰ Exercism Research is now launched. Help Exercism, help science and have some fun at research.exercism.io ðŸŽ‰

# 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. 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``````