蓝桥杯算法提高VIP-质数的后代

题目

题目链接

题解

欧拉筛+分解质因子。

通过欧拉筛将全部素数筛出来，对输入的数进行分解质因子，统计质因子个数，若等于2输出yes，其他输出no。

更新于2022.4.3

完全没必要分解质因数，直接统计完全部的素数后，遍历素数，如果n能整除该素数且商也是个素数则说明n为目标，如果不存在这种情况说明n不满足。

后一个代码实现的这个思路。

代码

#include
using namespace std;
const int N = 1e5+10;

int vis[N], prime[N], cnt;
int n, x;

int main()
{
	for(int i = 2;i >n;
	while(n--) {
		cin>>x;
		int res = 0, flag = 0;
		for(int i = 1;i  T;
	while (T --) {
		cin >> n;
		int flag = 0;
		for (int i = 0;prime[i]