Problem Link: http://oj.hecz.info:4000/problem/2

As the problem instructs, you are supposed to solve this function.

S_n = \sum_{k=1}^{n} \left[ \dfrac{(3k+6)!+1}{3k+7} – \left[ \dfrac{(3k+6)!}{3k+7} \right] \right]

Let’s take a look at it, considering the Wilson’s theorem, which says:

Only when p is a prime, ( p -1 )! ≡ -1 (\mod p )

It’s no hard to see the regular patterns, as you have to count all the primes in advance.

```
void getprime(int n) {
for (int i = 2; i <= n; ++i) {
if(used[i] == 0) prime[++tot]=i;
for(int j = 1; j <= tot; ++j) {
if (prime[j] * i > n) break;
used[prime[j] * i] = 1;
if (i % prime[j] == 0) break;
}
}
}
```

Then it’s the final program.

```
getprime(MAXN);
ans[0] = 0;
ans[1] = 0;
for (int i = 2; i <= 1e6; ++i) ans[i] = ans[i - 1] + !(used[3 * i + 7]);
```

## Leave a Reply