NOI-OJ 1.12 ID:10 素数对

整体思路

本题涉及大量素数的使用，故使用埃拉拖色尼算法提前计算出素数表可以避免大量、重复的计算。

判断素数对很简单，使用两个变量p1和p2代表素数表中的第一个和第二个素数，依次在表中向后移动，判断p2-p1是否等于2即可。

例程

#include<iostream>
#include<cmath>
using namespace std;
bool ss[10001];				//素数表
int  count;					//计数器
void altsn(int N){			//埃拉托色尼算法
	ss[0]=1;
	ss[1]=1;
	int p=2;
	while(p<=sqrt(N))
		if(ss[p]) p++;
		else{
			int times=2;
			while(p*times<=N)	{ ss[p*times]=1; times++;}
			p++;
		}
}

bool isP(int n){			//素数判断函数
	if(!ss[n])	return true;
	return false;
}

int main(){
	int N, p1=-1, p2=-1;
	cin>>N;
	altsn(N);				//造表
	for(int i=2; i<=N; i++){
		if(isP(i)){
			p1=p2, p2=i;
			if((p2-p1)==2)	{ printf("%d %d
", p1, p2); count++; }
		}
	}
	if(!count)	printf("empty");
	return 0;
}