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

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

On notera l'idiome tradionnel ifelse ifelse.

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

let rec decompose_aux u q = 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 :: decompose_aux v q else decompose_aux u (q + 1 + q mod 2) ;; let decompose u = if u <= 0 then failwith "decompose" else if u < 2 then [] else decompose_aux u 2 ;;

Le test u = 1 peut être déplacé dans la fonction decompose. En effet, on vérifie aisément que si u > 1 dans decompose_aux alors il en sera de même pour les appels récursifs.

La solution complète decompose.ml fait encore mieux, avec une suite des qi 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 :

q1 = 2,    q2 = 3,    q3 = 5,   q2n = q2n−1+2   (n ≥ 2),   q2n+1 = q2n+4 (n ≥ 2)

(On pourrait utiliser séparer decompose_aux en deux fonctions auxilliaires decompose_23 et decompose_suite pour refaire le test q>5 une fois qu'il a réussi.)