代码
#include <stdio.h>
#include <string.h>
#define MAX 100001
int isPrime[MAX];
int sum[MAX];
void selectPrime(){
for(int i=2; i<MAX; i++){
isPrime[i] = 1;
}
for(int i=2; i<MAX; i++){
if(isPrime[i]){
for(int j=i+i; j<MAX; j+=i){
isPrime[j] = 0;
}
}
}
}
void count(){
memset(sum, 0, sizeof(sum));
for(int i=4; i<MAX; i++){
if(isPrime[i] && isPrime[i-2]){
sum[i] = sum[i-1] + 1;
}
else{
sum[i] = sum[i-1];
}
}
}
int main(){
int num;
scanf("%d", &num);
selectPrime();
count();
printf("%d\n", sum[num]);
return 0;
}
注解
此题题意是找n以内的，差为2的素数，共有多少对。 因此关键问题是如何快速求素数。 采用筛法求素数的思想。即selectPrime()函数。先假设所有数都是素数。从2开始，2的倍数肯定都不是素数（一定有因子2）。同理，3的倍数也一定不是。一直找下去即可。 count()函数的作用是统计i和i-2都是素数，这样的素数对的数目。
此题学到的内容： （1）筛法求素数。 （2）hash打表，一次性计算出题目数据范围内的所有数，避免重复计算导致超时。 （3）memset函数赋初值0 #include <string.h> memset(sum, 0, sizeof(sum));
结果
