202406-小杨的幸运数字(luogu-P10720)

3
7
12
30

0
1
0

#include <iostream>
#include <cmath>

int main() {
    int n;
    std::cin >> n;                       // 读入待检测的正整数个数

    for (int i = 0; i < n; i++) {
        int a;
        std::cin >> a;                   // 读入当前待检测的正整数
        int count = 0;                   // 记录不同质因子的个数
        // 试除法枚举可能的质因子，只需到 sqrt(a)
        for (int j = 2; j <= sqrt(a); j++) {
            if (a % j == 0) {            // j 是 a 的一个质因子
                count++;                 // 发现新的质因子
            }
            // 将 a 中所有 j 因子全部除掉，避免重复计数
            while (a % j == 0) {
                a /= j;
            }
            // 提前退出：已经超过两种质因子，必定不是幸运数字
            if (count > 2) {
                break;
            }
        }
        // 若剩余 a>1，则剩下的 a 本身也是一个质因子
        if (a > 1) {
            count++;
        }
        // 恰好两种不同质因子则输出 1，否则输出 0
        std::cout << (count == 2 ? 1 : 0) << std::endl;
    }

    return 0;
}

#include <iostream>
#include <vector>

// 标记数组：is_primes[i]==0 表示 i 是质数；==1 表示合数
int is_primes[1000005];
// 线性筛得到的质数表，后续用于试除
std::vector<int> prime_nums;

int main() {
    int n;
    std::cin >> n;
    // 0 和 1 不是质数，先标记
    is_primes[0] = is_primes[1] = 1;

    // 线性筛（欧拉筛）预处理 1~1e6 的质数
    for (int i = 2; i <= 1000000; i++) {
        if (is_primes[i] == 0) {          // i 是质数，加入质数表
            prime_nums.push_back(i);
        }
        // 用当前质数表筛掉合数
        for (int num : prime_nums) {
            long long x = 1LL * i * num;    // 计算合数
            if (x > 1000000) {
                break;                      // 超出范围，退出
            }
            is_primes[x] = 1;               // 标记为合数
            if (i % num == 0) {
                break;                      // 保证每个合数只被最小质因子筛一次
            }
        }
    }

    // 处理每个询问
    for (int i = 0; i < n; i++) {
        int a;
        std::cin >> a;
        int count = 0;                      // 记录不同质因子个数
        // 用质数表试除，统计不同质因子
        for (int j = 0; j < prime_nums.size(); j++) {
            if (a % prime_nums[j] == 0) {   // 发现质因子
                count++;
            }
            if (count > 2) {                // 提前剪枝
                break;
            }
        }
        // 恰好两种质因子输出 1，否则 0
        std::cout << (count == 2 ? 1 : 0) << std::endl;
    }

    return 0;
}
}