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 do_rec q qq qqq x u = if u = 1 then [] else let v = u/q in if v < q then [u] else if u mod q = 0 then q::do_rec q qq qqq x v else do_rec qq qqq (qqq+x) (match x with 2 -> 4 | _ -> 2) u let decompose u = do_rec 2 3 5 2 u 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 verification 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 _ = verification m n