spoj-ocaml / 00002.PRIME1 / prime1.ml

(* https://www.spoj.pl/problems/PRIME1/ *)

let (|>) x y = y x

let max_s = 31622

let is_prime_t n =
  let sn = n |> float_of_int |> sqrt |> int_of_float in
  let rec ip_aux m =
    if      m >  sn      then true
    else if n mod m == 0 then false
    else                      ip_aux (m + 2)
  in
  n != 1 && (n == 2 || n mod 2 > 0 && ip_aux 3)

let is_prime =
  let primes =
    let rec calc_primes n accu =
      if      n > max_s    then List.rev accu
      else if is_prime_t n then calc_primes (n + 2) (n :: accu)
      else                      calc_primes (n + 2) accu
    in calc_primes 9 [7; 5; 3; 2]
  in
  function n ->
    let sn = n |> float_of_int |> sqrt |> int_of_float in
    let rec ip_aux = function
        []          -> true
      | p :: primes ->
          if      p > sn      then true
          else if n mod p > 0 then ip_aux primes
          else                     false
    in n != 1 && ip_aux primes

let solve n m =
  for i = n to m do
    if is_prime i then
      Printf.printf "%d\n" i
  done ;
  print_newline ()

let main () =
  let t = Scanf.scanf "%d\n" (fun t -> t) in
  for i = 1 to t do
    let n, m = Scanf.scanf "%d %d\n" (fun n m -> n, m) in
    solve n m
  done

let () = main ()
Tip: Filter by directory path e.g. /media app.js to search for public/media/app.js.
Tip: Use camelCasing e.g. ProjME to search for ProjectModifiedEvent.java.
Tip: Filter by extension type e.g. /repo .js to search for all .js files in the /repo directory.
Tip: Separate your search with spaces e.g. /ssh pom.xml to search for src/ssh/pom.xml.
Tip: Use ↑ and ↓ arrow keys to navigate and return to view the file.
Tip: You can also navigate files with Ctrl+j (next) and Ctrl+k (previous) and view the file with Ctrl+o.
Tip: You can also navigate files with Alt+j (next) and Alt+k (previous) and view the file with Alt+o.