1007 素数对猜想 (20)（20 分）

让我们定义 dn d n = pn+1 p n + 1 − pn p n ，其中 pn p n 是第i个素数。显然有 d1 d 1 =1 且对于n>1有 dn d n 是偶数。“素数对猜想”认为“存在无穷多对相邻且差为2的素数”。 现给定任意正整数N(N< 105 10 5 )，请计算不超过N的满足猜想的素数对的个数。 输入格式： 每个测试输入包含1个测试用例，给出正整数N。 输出格式： 每个测试用例的输出占一行，不超过N的满足猜想的素数对的个数。 输入样例：

20 1

输出样例：

4 1

杂

我看到的题目是这样的，感觉(＃°Д°)。我去百度了素数对猜想才明白题目中公式是什么。用latex重新把公式重新编辑了一遍。

解析

这题我的思路是：输入的数num，把 2~num 的素数过一遍。每算出一个素数，便和上一个素数作差。一个循环便可得到多少素数对。 完整代码：

#include<stdio.h> #include<math.h> int judge_prime(int num) { int i = 0; for(i=2; i<=sqrt(num) ;i++){ if(num%i ==0) return 0; } return 1; } int main() { int num = 0; scanf("%d",&num); int i = 0; int prime_part = 0; int prime=2; for(i=3; i<=num ;i++){ if(judge_prime(i) == 1){ if(i-prime == 2) prime_part++; prime = i; } } printf("%d",prime_part); return 0; }