Décomposition en facteurs premiers

Sans se fatiguer à optimiser quoique ce soit, on reprend simplement les règles dans l'ordre.

let rec decomp_rec q u = if u = 1 then [] else if u mod q = 0 then q::decomp_rec q (u/q) else decomp_rec (q+1) u ;; let decompose u = decomp_rec 2 u ;;

On notera l'idiome tradionnel if... else if... else.

À partir de ce code et avec un peu de réflexion on raffine pour utiliser les deux optimisations de l'énoncé.

(* q est q_i, qq est q_i+1 *) let rec decomp_rec q qq u = if u = 1 then [] else let v = u/q in (* éviter de diviser deux fois, diviser c'est cher *) if v < q then [u] (* liste du seul élément u, même chose que u::[] *) else if u mod q = 0 then q::decomp_rec q qq v else decomp_rec qq (qq+2) u ;; let decompose u = decomp_rec 2 3 u ;;

La solution complète decompose.ml fait encore mieux, avec une suite des q_i qui évite les multiples de 2 et de 3 en commençant par 2, 3, 5 puis en ajoutant alternativement 2 et 4. Plus précisément :

q₁ = 2, q₂ = 3, q₃ = 5, q_2n = q_2n-1+2 (n ≥ 2), q_2n+1 = q_2n+4 (n ≥ 2)