题目 1007 素数对猜想 (20分) 让我们定义Dn=Pn+1-Pn；Pi是第i个素数。显然D1=3-2=1，且对n>1有dn是偶数。 素数对猜想”认为“存在无穷多对相邻且差为2的素数”
现给定任意正整数N(<10**5)，请计算不超过N的满足猜想的素数对的个数。 输入格式: 输入在一行给出正整数N。
输出格式: 在一行中输出不超过N的满足猜想的素数对的个数。
输入样例: 20 输出样例: 4 代码长度限制 16 KB 时间限制 200 ms 内存限制 64 MB
思路 题目的意思是在一个给定的一个数中，找出其中全部的素数，然后求这些素数组成的素数对的个数。 例如 20 其中的素数按顺序排列是 2，3，5，7，11，13，17，19 素数对的个数分别是（5-3）（7-5）（13-11）（19-17） 很容易理解相邻素数差为2的素数对的意思。 因为符合要求素数对是相邻的，所以可以在从3到n判断素数时，用prior记录前一个素数，然后进行判断现在得到的素数和前一个素数是否成为素数对，然后更新prior为现在的。
int prior=3; for (int i = 3; i <= n; i++)//从三算是因为2肯定不满足条件 { if (isprime(i)) { if ((i - prior) == 2) count++; prior = i; } i++; }题目设置的时间限制是200ms，判断n是否是素数的时候如果从2到n进行判断容易超时。实际上我们只要从2到根号n,进行判断就好了。因为一个非素数，=至少会有一个小于等于根号n的因子。这样就不容易超时勒。
#include<iostream> #include<math.h> using namespace std; bool isprime(int n) { if (n == 1) //1不是素数 return false; for (int i = 2; i <= (int)sqrt(n); i++) if (n % i == 0) return false; return true; } int main() { int n; cin >> n; int count=0; //计算个数 int prior=3; //满足条件的素数对中第一个素数一定是3 for (int i = 3; i <= n; i++) { if (isprime(i)) { if ((i - prior) == 2) count++; prior = i; } i++; } cout << count; return 0; }