-
Notifications
You must be signed in to change notification settings - Fork 1
/
problem35.ml
79 lines (74 loc) · 1.97 KB
/
problem35.ml
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
let int_pow a b = truncate ((float a) ** (float b));;
let digitize number =
let rec aux num acc =
match num with
| n when n<10 -> (n::acc)
| n -> let digit = n mod 10 in
if ((digit = 2) || (digit = 4) || (digit = 6) || (digit = 8)) then []
else aux (n/10) (digit::acc)
in
aux number [];;
let undigitize lst =
let len = List.length lst in
let rec aux l fact acc =
match l with
| [] -> acc
| x::xs -> aux xs (fact/10) (acc+x*fact)
in
aux lst (int_pow 10 (len - 1)) 0
;;
let rotations (number : int list) =
let len = List.length number in
let rec aux lst i acc =
match (i,lst) with
| _,[] -> []
| i,_ when i = len -> acc
| 0,(x::xs) -> aux (xs@[x]) (i+1) acc
| i,(x::xs) -> aux (xs@[x]) (i+1) ((x::xs)::acc)
in
aux number 0 []
;;
(*count +5 for 2,3,5,7,11*)
let solve =
let bound = 999999.0 in
let lim = truncate (bound) in
let bitmap = Array.make (lim+1) true in
let sieve (n : float) =
let root = truncate (sqrt n) in
for i = 2 to root do
if (bitmap.(i) == true) then
let j = ref (i*i)
in
while (!j <= lim) do
bitmap.(!j) <- false;
j := !j + i;
done;
done;
in
let checkRotations num =
if (num = []) then false
else
let rec aux lst =
match lst with
| [] -> true
| (h::t) -> let number = (undigitize h) in
if (bitmap.(number)) then
(bitmap.(number) <- false;
aux t;)
else false
in
aux num
in
let counter = ref 0;
in
sieve bound;
Array.iteri (
fun indx value ->
if (value) then
(bitmap.(indx) <- false;
let numbers = rotations (digitize indx) in
if (checkRotations numbers) then
counter := (!counter)+(List.length numbers) + 1;)
) bitmap;
((!counter) + 5)
;;