Caml light and finding the prime factors

Question

I wrote the following Caml light code to find prime factors of a number (part of an early Project Euler question).

Largest prime factor

The prime factors of 13195 are 5, 7, 13 and 29.

What is the largest prime factor of the number 600851475143?

let rec find_factors target check =
if (check > (int_of_float (sqrt (float_of_int target)))) then [] else
        (find_factors target (check+1))@if target mod check == 0 then 
[ check; (target/check)] else[] ;;

let display n =
print_int n;print_newline();;

do_list display (find_factors 10 1);
print_newline();;

I'm very new to functional programming and I suspect I'm all over the place - if anyone would like to give me some tips that would be ideal. :)

Answer 1

I guess that I should not be giving you an answer, but guide you. So, one general remark that I have: stylistically, it would be preferable to see you start with

let largest_factor n =
    let rec aux_factor d n =
        ...
    in 
        # some expression involving to aux_factor 

The idea is that your solution function should be an expression of your problem and nothing else, so largest_factor number, not largest_factor number what_is_that.

Note that I am talking OCaml here, not sure if the pseudosample I wrote is cromulent Caml Light.

Answer 2

A couple of points regarding efficiency:

• You recompute the square root of target at every recursive call of find_factors. You can do better than that.

• You use list concatenation in a \$O(n)\$ algorithm: you can avoid it by prepending the values instead, and post process your result with a list reverse (List.rev).

@agravier's answer offers a good hint as to how you may optimize the above points while still supporting a decent interface for your function.

Consider the following functions, which calculate the sum of a list of integers:

let rec lsum l =
    match l with
        | [] -> 0
        | x::xs -> x + lsum xs

let rec lsum' acc l =
    match l with
        | [] -> acc
        | x::xs -> lsum (acc+x) xs

The first one provides a simple interface which corresponds exactly to the purpose of the function: it's easy to understand and use by just reading its signature. The second one is not as easy to understand (what's that acc parameter there?), but it is more efficient: it's a tail recursive definition, which may be optimized to a simple loop. You will want to write function in the second style, but with the interface of the first style.

(* simple interface *)
let lsum'' l =
    (* efficient implementation *)
    let rec lsum' acc l = ...
    in lsum' 0 l