让我们定义 dn 为：dn = pn+1 - pn，其中 pi 是第i个素数。显然有 d1=1 且对于n>1有 dn 是偶数。“素数对猜想”认为“存在无穷多对相邻且差为2的素数”。
现给定任意正整数N (< 10⁵)，请计算不超过N的满足猜想的素数对的个数。
输入格式：每个测试输入包含1个测试用例，给出正整数N。
输出格式：每个测试用例的输出占一行，不超过N的满足猜想的素数对的个数。
输入样例：
20
输出样例：
4
思路：创建一个10000的数组， 查找 0~N 的素数并存储到数组中， 然后在数组中查找素数对，并记录个数；
C语言：
#include <stdio.h>
int is_prime(int n);
const int N = 100000;
int main(void)
{
int prime[N];
int count = 0;
int n, flag;
scanf("%d", &n);
// 找素数
int i;
for (i=2; i<=n; i++){
if (is_prime(i)){
prime[count++] = i;
//printf("%d\n", i);
}
}
// 查找素数对对数
int sum = 0;
for (i=0; i<count-1; i++){
if (prime[i+1] - prime[i] == 2){
sum++;
}
}
printf("%d", sum);
return 0;
}
// 判断 n 是否为素数
int is_prime(int n)
{
int j;
int flag = 1;
for (j=2; j<n/2+1; j++){
if (n%j == 0){
flag = 0;
break;
}
}
return flag;
}
最后一个测试没有通过，超时了，看来要优化算法。
1107.jpg
用另一种方法重写了：
#include <stdio.h>
int main(void)
{
int n;
scanf("%d", &n);
int arr[n+1];
// 初始化为 1
int i, j;
for (i=2; i<n+1; i++){
arr[i] = 1;
}
// 将质数的倍数标记为非质素
for (i=2; i<n+1; i++){
if (arr[i] == 1){
for (j=2; i*j <= n; j++){
arr[i*j] = 0;
}
}
}
int count = 0;
int temp = 2; // 记录当前素数，前面的那位素数。
int num;
for (i=3; i<n+1; i++){
if (arr[i] == 1){
if (i - temp == 2){
count++;
}
temp = i;
}
}
printf("%d", count);
return 0;
}
构造素数表.jpg
