【深基7.例2】質數篩

題目描述

輸入 $n$ 個不大于 $10^5$ 的正整數。要求全部儲存在數組中，去除掉不是質數的數字，依次輸出剩余的質數。

輸入格式

第一行輸入一個正整數 $n$，表示整數個數。

第二行輸入 $n$ 個正整數 $a_i$，以空格隔開。

輸出格式

輸出一行，依次輸出 $a_i$ 中剩余的質數，以空格隔開。

樣例 #1

樣例輸入 #1

5
3 4 5 6 7

樣例輸出 #1

3 5 7

提示

數據保證，$1\le n\le 100$，$1\le a_i\le 10^5$。

思路

某個質數的倍數肯定不是質數。

AC代碼

#include <iostream>
#include <bitset>
#define AUTHOR "HEX9CF"
using namespace std;const int maxn = 100005;
bitset<maxn> vis;void init()
{vis[0] = 1;vis[1] = 1;for (int i = 2; i < maxn / i; i++){if (!vis[i]){for (int j = i * i; j <= maxn; j += i){vis[j] = 1;}}}
}int main()
{int n;init();cin >> n;for (int i = 0; i < n; i++){int t;cin >> t;if (!vis[t]){cout << t << " ";}}return 0;
}