题解 | #素数#

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

//这题练筛法

void Func68(void){
	//整理一下筛法的逻辑：
	//1.被筛掉的必是合数
	//2.任何一个合数可被分解质因数 这意味着 如果所有小于自己的质数都没把自己筛掉 自己就是质数 
	//3.结合1，被筛剩下的数中一定包含当前范围所有质数 
	//所以扫到当前数时，必已在其之前所有质数攻击下存活，其必是质数。 
	int n;
	while(scanf("%d",&n) != EOF){
		if (n<2 || n>10000){
			printf("Error!\n");
			exit(0);
		}
		vector<int> prime;
		bool Isprime[n];
		fill(Isprime,Isprime+n,true);
		for(int i=2; i<n; i++){
			if(!Isprime[i]){
				continue;
			}
			prime.push_back(i);//这里push进去就不用再扫一遍n这么大的数组 
			for(int j=i*i; j<n; j+=i){
				Isprime[j] = false;
			}
		}
		int begin = 0;
		for(int i=0; i<prime.size(); i++){//就看到了用vector的必要性 
			if(prime[i]%10 == 1){
				if(!begin){
					begin = 1;
					printf("%d",prime[i]);
				}else{
					printf(" %d",prime[i]);
				}
			}
		}
	}
}

int main(){
	Func68();
	return 0;
}