B1007 素数对猜想 (20分)

素数判断

1. 原文

让我们定义dn为：dn=pn+1−pn，其中pi是第i个素数。显然有d1=1，且对于n>1有dn是偶数。“素数对猜想”认为“存在无穷多对相邻且差为2的素数”。

现给定任意正整数N(<$10^5$)，请计算不超过N的满足猜想的素数对的个数。

输入格式:

输入在一行给出正整数N。

输出格式:

在一行中输出不超过N的满足猜想的素数对的个数。

输入样例:

20    

输出样例:

4

2. 解析思路

素数判断固定方法 isPrime()函数：素数是除了1和自身以外无约束的数

从3到n递增判断素数之间是否相差2

3. AC代码

#include<stdio.h>
#include<math.h>
bool isPrime(int n){
	if(n<2){
		return false;
	}
	int sqr=(int)sqrt(1.0*n);
	for(int i=2;i<=sqr;i++){
		if(n%i==0){
			return false;
		}
	}
	return true;
}

int main(){
	int n;
	scanf("%d",&n);
	int p0=2;
	int cnt=0;
	for(int i=3;i<=n;i++){
		if (isPrime(i))
		{
			if (i-p0==2)
			{
				//printf("%d %d\n",i,p0);
				cnt++;
			}
			p0=i;
		}
	}
	printf("%d\n", cnt);

	return 0;
}

4. 方法二

测试点5的耗时更少

#include<stdio.h>
int visit[100010]={};
int main(){
	int n;
	scanf("%d",&n);
	int p0=2;
	int cnt=0;
	for(int i=2;i<=n;i++){
		if(visit[i]==0){
			if(i-p0==2){
				cnt++;
			}
			p0=i;
			for(int j=i+i;j<=n;j+=i){
				visit[j]++;
			}
		}
	}
	printf("%d\n",cnt);

	return 0;
}