0%

Problem 574

Verifying Primes

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

• $A$ and $B$ have no prime factor in common, that is $\text{gcd}(A,B)=1$.
• The product $AB$ 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)$.

检验素数

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

$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$最小。