#open "sys";;

let eratos n =
        let t = make_vect ((n-1)/2) true
        and i = ref 0 and r = int_of_float (sqrt (float_of_int n)) in
        while !i*2+3 <= r do
                while not t.(!i) do incr i done;
                for j = !i to (n/(!i*2+3) -1) /2 -1 do t.((!i*2+3)*(2*j+3) /2 -1) <- false done;
                incr i;
        done;
        let l = ref [] in
        for j = (n-1)/2 -1 downto 0 do if t.(j) then l:= (2*j+3) :: !l done;
        t,(2::!l);
;;

let t = ref [||] and l = ref [] and nm = ref 0 and nl = ref 0 ;;

let init0 y n =
        if y || !nm < n then (
                let a,b = eratos n in
                t:= a ; l:= b ; nm:= n ; nl:= list_length b;
        );
;;

let init = init0 true ;;

init 32771;;


let factors0 b n =
        let rec pval p i = fun
                | n when n mod p = 0 -> pval p (i+1) (n/p)
                | n -> i,n
        in
        let rec aux = fun
                | 1 _ -> []
                | n (a::_) when a*a > n || a*a < 0 -> [n,1]
                | n (a::q) -> (let i,nn = pval a 0 n in
                               if i = 0 then aux n q else (if b then raise Exit else (a,i)::(aux nn q)))
                | n _ -> failwith ("décomposition inconnue de " ^ (string_of_int n))
        in
        aux n !l;
;;

let factors = factors0 false ;;

let isprime n =
        if n < 0 then failwith "borne max dépassée";
        try
                if !nm < n then factors0 true n = [n,1] else (
                if n = 1 then false else (if n = 2 then true else (if n mod 2 = 0 then false else !t.(n/2 -1))));
        with Exit -> false
;;

let pretty_string n =
        let aux1 p d =
                (string_of_int p) ^ match d with
                        | 1 -> ""
                        | 2 -> "²"   (* "\253" pour le bin mode *)
                        | 3 -> "³"   (* "\252" pour le bin mode *)
                        | d -> "^" ^ string_of_int d
        in
        let rec aux = fun
                | [] -> ""
                | [p,d] -> aux1 p d
                | ((p,d)::q) -> (aux1 p d) ^ "x" ^ (aux q)
        in 
        if n > 1 then (
                let f = factors n
                and nn = string_of_int n in
                if f = [n,1] then nn ^ " est premier."
                else nn ^ " = " ^ aux f;
        ) else "";
;;

let pretty_dec n = print_endline (pretty_string n) ;;


(* k_ième nombre premier *)

let ithprime k =
        if !nl < k && k < 564164 then (
                if interactive then init0 false 8388608
                else (
                        let kk = float_of_int k in
                        init (min (int_of_float (kk*.(log kk)*.1.14260611623)) 8388608);
                );
        );
        let rec aux = fun
                | [] _ -> failwith "borne max dépassée"
                | (a::_) 1 -> a
                | (_::q) n -> aux q (n-1)
        in
        if k < 564164 then aux !l k else (
                let i = ref 564164 and n = ref 8388617 in
                while !i < k do
                        n:= !n + 2;
                        if isprime !n then incr i;
                done;
                !n;
        );
;;

(* la fonction inverse de ithprime, nb de nb premiers <= n *)

let pi n =
        let b = !nm < n && n < 8388593 in
        if b && not interactive then (
                init n;
                !nl;
        ) else (
                if b then init0 false 8388608;
                let rec aux n i = fun
                        | [] -> i
                        | (a::_) when a > n -> i
                        | (_::q) -> aux n (i+1) q
                in
                if n < 8388593 then aux n 0 !l else (
                        let i = ref 564163 and a = ref (n-1 + n mod 2) in
                        while !a > 8388615 do
                                if isprime !a then incr i;
                                a:= !a - 2;
                        done;
                        !i;
                );
        );
;;


let nextprime n =
        let i = ref (n+1 + n mod 2) in
        while not isprime !i do i:= !i+2 done;
        !i;
;;

let prevprime n =
        let i = ref (n-1 - n mod 2) in
        while not isprime !i do i:= !i-2 done;
        !i;
;;


let main args =
        let err = "prime [is|ith|pi|next|prev] <n>" in
        try
                (try
                        let nn = args.(2) in let n = int_of_string nn in
                        match args.(1) with
                                | "is" -> if isprime n then print_endline (nn ^ " est premier.")
                                          else print_endline (nn ^ " est composé.");
                                          true
                                | "ith" -> print_endline ("le " ^ nn ^ "e nombre premier est " ^ 
                                                (string_of_int (ithprime n)));
                                           true
                                | "pi" -> print_endline ("pi(" ^ nn ^ ") = " ^ (string_of_int (pi n)));
                                          true
                                | "next" -> print_endline (" -> " ^ (string_of_int (nextprime n)));
                                            true
                                | "prev" -> print_endline (" -> " ^ (string_of_int (prevprime n)));
                                            true
                                | _ -> print_endline err ; false
                with Invalid_argument "vect_item" -> pretty_dec (int_of_string args.(1)) ; true)
        with | Invalid_argument "vect_item" -> print_endline err ; false
             | Failure "int_of_string" -> print_endline err ; false
             | Failure s -> print_endline s ; false
;;

if not interactive then (
        let b = main command_line in
        flush std_out;
        if b then exit 0 else exit 1;
);;