素数筛选（暴力排除）

本文主要是介绍素数筛选（暴力排除），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

前言：写这一题的时候没看到本质，只拿了一半的分，其实这一题就是找最小匹配的素数

而且我还忘记去重导致一半的样例没过

题目地址
在这里插入图片描述

法一：直接先去重，后对每一个数作为因子，开一个桶记录

#include<iostream>
#include<bits/stdc++.h>
#include<set>
#include<map>
using namespace std;#define endl "\n"
#define ll long longvoid solve(){int n;cin>>n;vector<int> a(n);for(int&x:a) cin>>x;int m = 2*n + 10;vector<int> dp(m,0);set<int> se(a.begin(),a.end());for(int x:se){for(int j = x; j<m;j+=x){dp[j] = 1;}}for(int i = 2;i<m;i++){if(dp[i] == 0){cout<<i<<endl;return;}}
}signed main(){cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);ll t;cin>>t;while(t--)solve();
}

法二：先进行素数筛

#include<bits/stdc++.h>using i64 = long long;
using u64 = unsigned long long;std::bitset<10000005>st;//定义方式，这里就相当于定义bool数组
//st[i]==0,则i为素数
std::vector<int>Prime(2e5 + 5);//存质数,下标从1开始输出第几个质数就输出prime(n)；
void pri(int M)
{int cnt = 0;for (int i = 2; i <= M; i++){if (st[i] == 0)    Prime[++cnt] = i;if (cnt > 2e5) break;for (int j = 1; j <= cnt; j++){if (i * Prime[j] > M)break;// 如果超出给出的范围，那么就退出循环 st[i * Prime[j]] = 1;//素数的倍数不是素数，进行标记。if (i % Prime[j] == 0)break;//超级关键的只标记一次}}
}void solve() {int n;std::cin >> n;std::unordered_map<int, int> mp;for (int i = 1; i <= n; i++) {int a;std::cin >> a;mp[a] = 1;}for (int i = 1; i <= 200001; i++) {if (!mp[Prime[i]]) {std::cout << Prime[i] << '\n';return;}}
} signed main() {std::ios::sync_with_stdio(0);std::cout.tie(0);std::cin.tie(0);pri(10000000);i64 t = 1; std::cin >> t;while (t--) {solve();}
}