# Hi, I'm Ataias Reis

Programmer, made in Brazil, Alma mater University of Brasilia

# Get number of common divisors in OCaml

Hi, everyone! In this challenge I used OCaml sets again. The goal was to get the number of common divisors for each pair of numbers in the test cases. The first function I wrote was to define a limit until when I would be checking if the number was divisible or not:

``````(* Need to check divisors just up to sqrt x *)
let max x = Int.of_float (sqrt x) |> (+) 1;;
``````

After that, I wrote a function to get the number of common divisors of a single number `n`. Inside it I wrote another function, `divs` responsible to get all the divisors up to the limit define in the `max` function. This is just half of the divisors. The other half is obtained by dividing `n` by its divisors and adding each result in the set. For instance, if `n` has divisors, up to `max n` in the set `set`, then I add the rest using:

``````let f s x = Set.add s (n / x) in
Set.fold set ~init:set ~f:f
``````

In the end, the whole function to get the divisors is

``````let get_divisors n =
let c = Int.comparator in
(* Cap is the limit for the iterations *)
(* This is sqrt(n) *)
let cap = max (Float.of_int n) in
let set = Set.empty ~comparator:c in
let rec divs set i =
if n mod i = 0 then
let set = Set.add set i in
divs set (i+1)
else
if i > cap then set else divs set (i+1)
(* This set does not have all divisors
As the pairs are missing*)
in let set = divs set 1 in
(* Add the missing pairs *)
let f s x = Set.add s (n / x) in
Set.fold set ~init:set ~f:f;;
``````

After that, I could just get the divisors of each input, intersect the sets and then get the length of this set, which would be the number of common divisors:

``````let get_number_common_divisors n m =
let divs_n = get_divisors n in
let divs_m = get_divisors m in
let common = Set.inter divs_n divs_m in
Set.length common;;
``````

Finally, I needed some IO:

``````(* IO Code *)

(* When parsing with String.split,
some elements may be empty,
so we remove them *)
let remove_empty l =
let not_empty x = x <> "" in
List.filter ~f:not_empty l

(* Magic happens, returns list of numbers*)
let parse line =
let l = String.split line ~on:' ' in
let number_str = remove_empty l in
List.map number_str ~f:Int.of_string

let () = for i = 1 to n_tests do
let line = read_line () in
let l = parse line in
let a, b = match l with
| x::y::tl -> x, y
| _ -> 0, 0 in
print_int (get_number_common_divisors a b);
print_newline ();
done
``````

You can check the whole code on GitHub. If you want to compile this code, you could use:

``````\$ corebuild get_divisors.native
``````

An example of input/output:

``````# input
2
2 4
144 288
# output
2
15
``````