竞赛题优化：如何在指定时间内查找M*M矩阵中恰有3个因数的元素？

1. 替换素数判断算法：改用米勒-拉宾素性测试 #

你的prime函数是朴素试除法，对于大素数（目标位置很大时，对应的num会非常大），试除法效率极低。米勒-拉宾素性测试是概率性素数判断算法，针对64位整数，使用固定底数可实现确定性判断，速度比试除法快几个数量级。

实现示例：

#include <cstdint>
using namespace std;

bool is_prime(uint64_t n) {
    if (n <= 1) return false;
    if (n <= 3) return true;
    if (n % 2 == 0) return false;
    // 将n-1分解为d*2^s
    uint64_t d = n - 1;
    int s = 0;
    while (d % 2 == 0) {
        d /= 2;
        s++;
    }
    // 64位整数确定性判断的底数集合
    uint64_t bases[] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37};
    for (uint64_t a : bases) {
        if (a >= n) continue;
        uint64_t x = 1;
        uint64_t temp = d;
        uint64_t base = a % n;
        // 快速幂计算a^d mod n，用__int128避免溢出
        while (temp > 0) {
            if (temp % 2 == 1) {
                x = (__int128)x * base % n;
            }
            base = (__int128)base * base % n;
            temp /= 2;
        }
        if (x == 1 || x == n - 1) continue;
        bool composite = true;
        for (int j = 1; j < s; j++) {
            x = (__int128)x * x % n;
            if (x == n - 1) {
                composite = false;
                break;
            }
        }
        if (composite) return false;
    }
    return true;
}

2. 预生成素数：改用欧拉筛（线性筛）替代逐个判断 #

如果目标位置elem超过1e6，逐个判断素数的效率依然不足。可利用欧拉筛预生成素数，先通过素数定理估算第elem个素数的范围，再批量生成素数直到收集到目标数量。

示例思路：

#include <vector>
#include <cmath>

vector<uint64_t> generate_primes(int k) {
    vector<uint64_t> primes;
    if (k == 0) return primes;
    // 素数定理估算第k个素数的上限，加冗余避免估算不足
    double lnk = log(k);
    double lnlnk = log(lnk);
    uint64_t upper = (uint64_t)(k * (lnk + lnlnk)) + 100;
    // 欧拉筛生成素数
    vector<bool> is_prime(upper + 1, true);
    is_prime[0] = is_prime[1] = false;
    for (uint64_t i = 2; i <= upper; i++) {
        if (is_prime[i]) {
            primes.push_back(i);
            if (primes.size() == k) break;
        }
        for (uint64_t p : primes) {
            if (i * p > upper) break;
            is_prime[i * p] = false;
            if (i % p == 0) break;
        }
    }
    // 若估算上限不足，扩大范围补充素数
    while (primes.size() < k) {
        upper *= 2;
        vector<bool> new_is_prime(upper + 1, true);
        for (uint64_t p : primes) {
            for (uint64_t j = p * p; j <= upper; j += p) {
                new_is_prime[j] = false;
            }
        }
        for (uint64_t i = primes.back() + 1; i <= upper; i++) {
            if (new_is_prime[i]) {
                primes.push_back(i);
                if (primes.size() == k) break;
            }
        }
    }
    return primes;
}

之后在main中直接调用该函数获取第elem个素数，平方输出即可。

3. 简化矩阵位置计算逻辑 #

你的elem计算可以简化，提升可读性的同时减少冗余运算：

int elem;
if (row % 2 == 1) {
    elem = (row - 1) * side + col;
} else {
    elem = row * side - col + 1;
}

4. 细节优化 #

• 统一使用uint64_t类型，避免溢出问题，类型定义更明确。
• 移除main中row==1 && col==1的特殊判断，因为第1个素数是2，平方为4，和通用逻辑完全一致，无需单独处理。

内容的提问来源于stack exchange，提问作者user19266617