Problem 574

Verifying Primes

Let $q$ be a prime and $A \geq B > 0$ be two integers with the following properties:

$A$ and $B$ have no prime factor in common, that is $gcd (A, B) = 1$ .
The product $A B$ is divisible by every prime less than q.

It can be shown that, given these conditions, any sum $A + B < q^{2}$ and any difference $1 < A - B < q^{2}$ has to be a prime number. Thus you can verify that a number $p$ is prime by showing that either $p = A + B < q^{2}$ or $p = A - B < q^{2}$ for some $A, B, q$ fulfilling the conditions listed above.

Let $V (p)$ be the smallest possible value of $A$ in any sum $p = A + B$ and any difference $p = A - B$ , that verifies $p$ being prime. Examples:
$V (2) = 1$ , since $2 = 1 + 1 < 2^{2}$ .
$V (37) = 22$ , since $37 = 22 + 15 = 2 \cdot 11 + 3 \cdot 5 < 7^{2}$ is the associated sum with the smallest possible $A$ .
$V (151) = 165$ since $151 = 165 - 14 = 3 \cdot 5 \cdot 11 - 2 \cdot 7 < 13^{2}$ is the associated difference with the smallest possible $A$ .

Let $S (n)$ be the sum of $V (p)$ for all primes $p < n$ . For example, $S (10) = 10$ and $S (200) = 7177$ .

Find $S (3800)$ .

检验素数

取素数 $q$ 及整数 $A \geq B > 0$ 满足以下性质：

$A$ 和 $B$ 没有相同的质因数，也就是说 $gcd (A, B) = 1$ 。
乘积 $A B$ 能被所有小于 $q$ 的素数整除。

可以证明，在上述条件下，满足 $A + B < q^{2}$ 的两数之和，以及满足 $1 < A - B < q^{2}$ 的两数之差，一定是素数。因此你可以寻找满足上述条件的的 $A, B, q$ ，使得 $p$ 能写成 $p = A + B < q^{2}$ 或 $p = A - B < q^{2}$ 的形式，以此来验证 $p$ 是素数。

对于任意素数 $p$ ，记 $V (P)$ 为使得 $p$ 能表达为两数之和 $p = A + B$ 或两数之差 $p = A - B$ 的最小整数 $A$ 。例如：
$V (2) = 1$ ，因为 $2 = 1 + 1 < 2^{2}$ 。
$V (37) = 22$ ，因为 $37 = 22 + 15 = 2 \cdot 11 + 3 \cdot 5 < 7^{2}$ 能表达为两数之和且 $A$ 最小。
$V (151) = 165$ ，因为 $151 = 165 - 14 = 3 \cdot 5 \cdot 11 - 2 \cdot 7 < 13^{2}$ 能表达为两数之差且 $A$ 最小。

记 $S (n)$ 为所有素数 $p < n$ 对应的 $V (p)$ 之和。例如， $S (10) = 10$ ， $S (200) = 7177$ 。

求 $S (3800)$ 。