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
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
|
#include <stdio.h>
/* The digital root (also repeated digital sum) of a non-negative
* integer is the (single digit) value obtained by an iterative process
* of summing digits, on each iteration using the result from the previous
* iteration to compute a digit sum. The process continues until a
* single-digit number is reached.
*/
/* bit 0-2: top, mid, bottom
* bit 3-6: top-left, top-right, bottom-left, bottom-right
*/
enum {
TOP = 1,
MID = 2,
BOTTOM = 4,
TL = 8,
TR = 16,
BL = 32,
BR = 64
};
unsigned char lines[10] = {
TOP | BOTTOM | TL | TR | BL | BR,
TR | BR,
TOP | MID | BOTTOM | TR | BL,
TOP | MID | BOTTOM | TR | BR,
MID | TL | TR | BR,
TOP | MID | BOTTOM | TL | BR,
TOP | MID | BOTTOM | TL | BL | BR,
TOP | TL | TR | BR,
TOP | MID | BOTTOM | TL | TR | BL | BR,
TOP | MID | BOTTOM | TL | TR | BR
};
int popcount(unsigned char x)
{
int count = 0;
while (x) {
count += (x&1);
x >>= 1;
}
return count;
}
void get_digits(int x, int a[])
{
int i = 0;
do {
a[i] = x % 10;
x /= 10;
i++;
} while (x);
a[i] = -1;
}
int clock_sam(int x)
{
int digits[10];
int l = 0;
while (x >= 10) {
get_digits(x, digits);
x = 0;
for (int i = 0; digits[i] != -1; i++) {
l += popcount(lines[digits[i]]) * 2;
x += digits[i];
}
}
l += popcount(lines[x]) * 2;
return l;
}
int clock_max(int x)
{
int digits[10],next_digits[10], nx;
int l = 0;
get_digits(x, digits);
nx = 0;
for (int i = 0; digits[i] != -1; i++) {
l += popcount(lines[digits[i]]);
nx += digits[i];
}
while (x >= 10) {
get_digits(nx, next_digits);
int i;
/* calculate the diff */
for (i = 0; next_digits[i] != -1; i++) {
l += popcount(lines[digits[i]]^lines[next_digits[i]]);
}
while (digits[i] != -1) {
l += popcount(lines[digits[i]]);
i++;
}
/* get the next */
x = nx;
nx = 0;
for (i = 0; next_digits[i] != -1; i++) {
digits[i] = next_digits[i];
nx += next_digits[i];
}
digits[i] = -1;
}
l += popcount(lines[x]);
return l;
}
int isoddprime(int x)
{
for (int i = 3; i*i <= x; i += 2) {
if (x % i == 0)
return 0;
}
return 1;
}
int main()
{
int sum = 0;
const int A = 10*1000*1000;
const int B = 20*1000*1000;
for (int i = A+1; i < B; i += 2) {
if (isoddprime(i)) {
sum += clock_sam(i) - clock_max(i);
}
}
printf("%d\n", sum);
}
|
