lundi 1 mars 2010

Project Euler #3

#load "nums.cma"

open Big_int;;

let num = big_int_of_string "600851475143";;

let solution n =
  let rec factorize m p =
    if ge_big_int p m then
      Printf.printf "%s\n" (string_of_big_int m)
    else
      if eq_big_int (mod_big_int m p) zero_big_int then
        factorize (div_big_int m p) (big_int_of_int 2)
      else
        factorize m (succ_big_int p)
  in
  factorize n (big_int_of_int 2);;

solution num;;

Решение вида "а давайте-ка найдем все простые числа до sqrt(N), а потом найдем максимальное, которое разделит N без остатка", что прокатило для C++, в Ocaml оказалось неосуществимо в разумные сроки ;)

Aucun commentaire:

Enregistrer un commentaire