open Printf (* Méthode d'Euclide *) let rec euclide u v = if v = 0 then u else euclide v (u mod v) (* Méthode du collège *) let rec decompose_aux u q x = let v = u / q in if v < q then [ u ] else if u mod q = 0 then q::decompose_aux v q x else decompose_aux u (q + x) (if q < 5 then 2 else x mod 4 + 2) ;; let decompose u = if u < 1 then failwith "decompose" else if u = 1 then [] else decompose_aux u 2 1 ;; let rec communs xs ys = match xs,ys with | [],_ -> [] | _,[] -> [] | x::rx, y::ry -> if x < y then communs rx ys else if y < x then communs xs ry else (* x=y *) x::communs rx ry let rec produit xs = match xs with | [] -> 1 | x::xs -> x*produit xs let college u v = let us = decompose u and vs = decompose v in produit (communs us vs) (* Comparaison *) let zyva m n = printf "Vérification, %d essais, sur [1..%d]\n" n m ; let nfail = ref 0 in for i = 1 to n do let u = 1 + Random.int m and v = 1 + Random.int m in let p1 = euclide u v and p2 = college u v in if p1<>p2 then begin nfail := !nfail + 1 ; printf "Échec pour u=%d, v=%d: euclide=%d, college=%d\n" u v p1 p2 ; flush stdout end done ; if !nfail > 0 then printf "Il y a eu %d échec%s\n" !nfail (if !nfail > 1 then "s" else "") else printf "Que des succès\n" let m = int_of_string Sys.argv.(1) and n = int_of_string Sys.argv.(2) let _ = zyva m n ; exit 0