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 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é.
| 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 :
(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.)