题目描述

输入 $n$ 个不大于 $10^6$ 的正整数。要求全部储存在数组中，去除掉不是质数的数字，依次输出剩余的质数。

输入格式

第一行输入一个正整数 $n$，表示整数个数。

第二行输入 $n$ 个正整数 $a_i$，以空格隔开。

输出格式

输出一行，依次输出 $a_i$ 中剩余的质数，以空格隔开。

样例

5
3 4 5 6 7

3 5 7

说明/提示

数据保证，$1\le n\le100000$，$1 \leq a_i \leq 10^6$。

完成程序

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

const int MAX = 1000000;
int n;
bool f[MAX+1];

// 埃氏筛选法，筛除掉所有不是质数的数（在数组中留一个标记就是筛除）
void func(){
	f[1] = true;  // 1 既不是质数，也不是合数
	for(int i=__填空(1)__;__填空(2)__<=MAX;i++){
		if(!f[i]){
			for(int j=__填空(3)__;j<=MAX;j=__填空(4)__)
				f[j] = true;
		}
	}
}

int main(){

	scanf("%d", &n);
	func();

	int a;
	while(n--){
		scanf("%d", &a);
		if(__填空(5)__) printf("%d ", a); // 没有打标记的就是质数
	}

	return 0;
}

填空(1): {{ input(1) }}

填空(2): {{ input(2) }}

填空(3): {{ input(3) }}

填空(4): {{ input(4) }}

填空(5): {{ input(5) }}