## lundi 3 mai 2010

### Project Euler #35

let is_prime n =
if n < 0 then
false
else
let lim = int_of_float (sqrt (float_of_int n)) in
let rec check_mod i l =
if i > l then
true
else
if n mod i = 0 then
false
else
true && (check_mod (succ i) l)
in
check_mod 2 lim;;

let primes n =
let rec inner_primes i =
if i > n then
[]
else
if is_prime i then
[i] @ inner_primes (succ i)
else
inner_primes (succ i)
in
inner_primes 2;;

let circulations n =
let rec circulate str =
let str_len = String.length str in
if str_len = 1 then
[int_of_string n]
else
let variant = (String.sub str 1 (str_len - 1)) ^ (String.sub str 0 1) in
if variant = n then
[(int_of_string variant)]
else
[(int_of_string variant)] @ (circulate variant)
in
circulate n;;

(*
let is_circular n primes =
let number_string = string_of_int n in
let variants = circulations number_string in
List.fold_left 
    (&&)
    true
    (List.map
      (fun x -> List.exists (fun y -> (x = y)) primes)
      variants);;
*)

let is_circular n =
let number_string = string_of_int n in
let variants = circulations number_string in
List.fold_left (&&) true (List.map (is_prime) variants);;

let primes_till_1e6 = primes 1000000;;
let test_primes = primes_till_1e6;;

Printf.printf "%d\n"
(List.fold_left
(+)
0
(List.map
(fun x -> if (is_circular x) then 1 else 0 )
test_primes));;

Strange thing: List.exists is quite slow, so when I switched from using List.exists (commented out) to just plain is_prime in is_circular it became possible to get result in a minute. Or maybe I just can't use List.exists properly.