素数

http://t.cn/AiCulqtW

描述

输入一个整数n(2<=n<=10000)，要求输出所有从1到这个整数之间(不包括1和这个整数)个位为1的素数，如果没有则输出-1。

输入描述：

输入有多组数据。 每组一行，输入n。

输出描述：

输出所有从1到这个整数之间(不包括1和这个整数)个位为1的素数(素数之间用空格隔开，最后一个素数后面没有空格)，如果没有则输出-1。

示例1

输入：

100

输出：

11 31 41 61 71

#define _CRT_SECURE_NO_WARNINGS 1
#include <bits/stdc++.h>
using namespace std;

const int N = 1e4 + 1;
vector<int> prime;//保存质数
bool isPrime[N];//标记数组

void Initial() {
	for (int i = 0; i < N; ++i)
		isPrime[i] = true;
	isPrime[0] = isPrime[1] = false;
	for (int i = 2; i < N; ++i) {
		if (!isPrime[i])//非质数跳过
			continue;
		prime.push_back(i);
		for (int j = i * i; j < N; j += i)
			isPrime[j] = false;//质数的倍数为非质数
	}
	return;
}

int main() {
	Initial();
	int n;
	while (cin >> n)
	{
		bool isOutput = false;//判断是否有输出
		for (int i = 0; i < prime.size() && prime[i] < n; ++i) {
			if (prime[i] % 10 == 1) {
				isOutput = true;
				printf("%d ", prime[i]);
			}
		}
		if (!isOutput)
			printf("-1");
		printf("\n");
	}
	return 0;
}