题解 | 质数

题目链接

埃氏筛法：高效找出自然数范围内所有素数。

用埃氏筛法打表出2-10000范围内的所有素数，x后面添加的数不能有前导0（仅输出最小那个）：

判断x加1位，x1-x9中是否有质数；

判断x加2位，x10-x99中是否有质数；

#include<stdio.h>
#include<vector>
using namespace std;
vector<int> num(10001);//0-10000全标记为质数
vector<int> prime;

//埃氏筛法
void is_prime() {
	//0和1标记为不是质数
	num[0] = 1;
	num[1] = 1;
	for (int i = 2; i < 10001; i++) {
		if (num[i] == 0) {
			prime.push_back(i);//打表保存2-10000的质数
			//从 i*i 开始，将 i 的所有倍数标记为非素数
			for (int j = i * i; j < 10001; j = j + i) {
				num[j] = 1;
			}
		}
	}
}

int main() {
	is_prime();
	int t,x;
	while (scanf("%d", &t) != EOF) {
		for (int i = 0; i < t; i++) {
			scanf("%d", &x);
			for (int j =0; j < prime.size(); j++) {
				//x加1位，x1-x9中有质数
				if (prime[j]>=x*10+1 && prime[j]<=x*10+9){
					printf("%d\n", prime[j]);
					break;
				}
				//x加2位，x10-x99中有质数
				if (prime[j] >= x * 100 + 10 && prime[j] <= x * 100 + 99) {
					printf("%d\n", prime[j]);
					break;
				}
			}
			
		}
	}
	return 0;
}