NOI-OJ 1.13 ID:23 区间内的真素数

整体思路

这里需要大量使用素数，必须能够想到只求出M到N之间的素数是不够的，因为M到N之间数字的反序有可能是大于M或小于N的数字，例如M=2，N=20，那么19的反序91大于20，所以使用埃拉拖色尼算法计算素数表的时候要让范围尽可能大，根据题目要求，设计为1～100000。
本题也可以尝试不使用阿拉托色尼算法，对M和N之间的每一个数及其反序进行素数判断。
本题的难点是求反序，方法较多，例程中提供两种技巧供参考：

例程

#include<iostream>

#include<cmath>

#include<cstring>

using namespace std;

bool ss[100001];			//素数表

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 rev(int n){							//反序方法1

	char s1[10],s2[10];

	int len, reverse;

	sprintf(s1, "%d", n);				//sprintf输出到数组s1

	len=strlen(s1);						//反序复制到s2

	for(int i=0; i<len; i++)	s2[len-1-i]=s1[i];

	s2[len]='\0';						//将s2补全为字符串

	sscanf(s2, "%d", &reverse);			//使用sscanf从s2中提取一个int

	return reverse;

}

int rev2(int n){						//反序方法2

	int weishu=0;						//n的位数

	int reverse=0;

	int t=n;

	while(t){							//计算n的位数

		weishu++;

		t/=10;

	}

	t=n;

	while(t){							//循环计算反序数值reverse

		reverse+=(t%10)*pow(10, --weishu);

		t/=10;

	}

	return reverse;

}

int main(){

	int M, N;

	cin>>M>>N;

	altsn(100000);

	for(int i=M; i<=N; i++)

		if(isP(i) && isP(rev(i))){		//如果i和i的反序都是素数

			count++;

			if(count==1)				//第一次输出只输出数字

				printf("%d", i);

			else						//以后每次先输出逗号，再输出数字

				printf(",%d", i);

		}

	if(!count)	printf("No");

	return 0;

}

巴特西

NOI-OJ 1.13 ID:23 区间内的真素数

整体思路

例程

最新文章

热门文章