寻找绝对欧拉伪素数（AEPSP）的C++程序优化求助

你的程序运行缓慢的核心原因是错误且低效的判断逻辑——遍历所有a从2到n的时间复杂度是O(n)，完全无法处理大数值范围。以下是针对性的优化方案：

一、纠正核心逻辑错误 #

原程序仅检查a^((n-1)/2) ≡1 mod n，但根据AEPSP的定义，应允许结果为±1 mod n（即1或n-1）。这个错误会导致大量符合条件的数被误判，同时做了不必要的严格校验。

二、用数论性质替代全量遍历 #

AEPSP的本质是满足特定素因子条件的奇合数，无需遍历所有与n互质的a。根据数论，AEPSP的等价判定条件为：
n是无平方因子的奇合数，且对其每个素因子p：

• 若p ≡1 mod4，则p-1必须整除(n-1)/2；
• 若p ≡3 mod4，则p-1必须整除n-1。

基于此，我们可以彻底重构判断流程，将时间复杂度从O(n)降至O(√n)（素因子分解的时间）。

三、关键模块优化 #

1. 高效素性测试：替换遍历为Miller-Rabin测试 #

对于32位整数，使用固定基的Miller-Rabin测试可以在O(k log³n)时间内准确判断素性（k为测试基的数量，取12个基即可覆盖所有32位整数），远快于遍历到√n的试除法。

示例代码：

inline unsigned int pow_mod(unsigned int a, unsigned int n, unsigned int p) {
    unsigned long long res = 1;
    unsigned long long base = a % p;
    while (n > 0) {
        if (n & 1) res = (res * base) % p;
        base = (base * base) % p;
        n >>= 1;
    }
    return static_cast<unsigned int>(res);
}

bool is_prime(unsigned int n) {
    if (n <= 1) return false;
    if (n <= 3) return true;
    if (n % 2 == 0) return false;
    
    unsigned int d = n - 1;
    int s = 0;
    while ((d & 1) == 0) {
        d >>= 1;
        s++;
    }
    
    const int bases[] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37};
    for (int a : bases) {
        if (a >= n) continue;
        unsigned long long x = pow_mod(a, d, n);
        if (x == 1 || x == n - 1) continue;
        bool composite = true;
        for (int j = 1; j < s; j++) {
            x = (x * x) % n;
            if (x == n - 1) {
                composite = false;
                break;
            }
        }
        if (composite) return false;
    }
    return true;
}

2. 快速素因子分解 #

结合试除法与Miller-Rabin测试，先试除小素数，剩余部分用Miller-Rabin判断是否为素数，避免不必要的遍历：

#include <vector>
using namespace std;

vector<unsigned int> factorize(unsigned int n) {
    vector<unsigned int> factors;
    if (n % 2 == 0) {
        factors.push_back(2);
        while (n % 2 == 0) n /= 2;
    }
    for (unsigned int p = 3; p * p <= n; p += 2) {
        if (n % p == 0) {
            factors.push_back(p);
            while (n % p == 0) n /= p;
        }
    }
    if (n > 1) factors.push_back(n);
    return factors;
}

3. 重构AEPSP判断函数 #

基于数论条件，直接验证素因子的约束：

bool is_aepsp(unsigned int n) {
    if (n % 2 == 0) return false;
    if (is_prime(n)) return false; // 只找合数
    
    vector<unsigned int> factors = factorize(n);
    // 检查是否有平方因子（因子列表中无重复）
    for (size_t i = 1; i < factors.size(); i++) {
        if (factors[i] == factors[i-1]) return false;
    }
    
    unsigned int half_n_minus_1 = (n - 1) / 2;
    for (unsigned int p : factors) {
        if (p % 4 == 1) {
            if (half_n_minus_1 % (p - 1) != 0) {
                return false;
            }
        } else { // p %4 ==3
            if ((n - 1) % (p - 1) != 0) {
                return false;
            }
        }
    }
    return true;
}

四、进阶优化：批量生成候选数 #

逐个检查n的效率仍较低，可直接根据素因子条件生成候选数：

1. 预先筛选满足条件的素数集合（比如p≡1 mod4且p-1能整除某个数的一半，或p≡3 mod4且p-1能整除某个数）；
2. 组合这些素数相乘得到n，再验证是否符合AEPSP条件。

这种生成式的方法可以跳过大量无效的n，大幅提升大数值范围的查找效率。

五、其他细节优化 #

• 将频繁调用的函数（如pow_mod）声明为inline，减少函数调用开销；
• 避免重复计算：比如(n-1)/2只需计算一次；
• 优化IO：将结果存入缓冲区后批量输出，减少printf的调用次数。

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