GESP2024年6月认证C++五级( 第三部分编程题（2））

参考程序（线性筛法）

#include <iostream>
#include <vector>
using namespace std;

const int MAXN = 10000001;  // 最大数字范围

// 保存每个数的质因子数量
vector<int> primeFactors(MAXN, 0);

void linearSieve() {
    // 从 2 开始筛选
    for (int i = 2; i < MAXN; i++) {
        // 如果 i 是质数
        if (primeFactors[i] == 0) {
            // 质数的质因子数是 1（它自己）
            primeFactors[i] = 1;
            // 从 i 的倍数开始更新质因子数量
            for (int j = i * 2; j < MAXN; j += i) {
                primeFactors[j]++;
            }
        }
    }
}

int main() {
    int t;
    cin >> t;

    // 预处理质因子数量
    linearSieve();

    while (t--) {
        int n;
        cin >> n;

        // 判断该数字是否是幸运数字
        if (primeFactors[n] == 2) {
            cout << "1\n";
        } else {
            cout << "0\n";
        }
    }

    return 0;
}

参考程序（因数分解法）

#include<bits/stdc++.h>
using namespace std;
map<int,int> mp;
const int N = 1e5+10;
int calc(int x) 
{
	int res = 0;
	set<int> s;
	for (int i = 2; i * i <= x; i++) 
	{
		if (x % i == 0) 
		{
			s.insert(i);
			while (x% i == 0)
			{
				x/= i;
			}
		}
	}
	if (x != 1) 
	{
		s.insert(x);
	}
	return (int)s.size();
}
int a[N];
int main()
{
	int n;
	cin>>n;
	long long ans = 0;
	int pre = 0;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i];
		int x = calc(a[i]);
		if(x==2)
			cout<<"1\n";
		else 
			cout<<"0\n";
	}
}