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)
      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 n_tests = read_int ();;
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 ();

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 4
144 288
# output

Thanks for reading!

comments powered by Disqus