C++编写程序费马素性测试，32位整数

### C++ 费马素性测试 32位整数 示例代码 费马素性测试是一种基于费马小定理的概率性算法，用于判断一个数是否为素数。根据费马小定理，如果 \( p \) 是一个素数，且 \( a \) 是一个小于 \( p \) 的正整数，则满足以下关系： \[ a^{p-1} \mod p = 1 \] 下面是一个适用于 32 位整数的 C++ 实现示例代码，使用费马素性测试来判断一个数是否可能是素数。 ```cpp #include <iostream> #include <cstdlib> #include <ctime> using namespace std; // 快速幂取模函数 unsigned int powerMod(unsigned int base, unsigned int exp, unsigned int mod) { unsigned int result = 1; base = base % mod; while (exp > 0) { if (exp & 1) { result = (result * base) % mod; } base = (base * base) % mod; exp >>= 1; } return result; } // 费马素性测试函数 bool fermatTest(unsigned int n, int iterations = 5) { if (n <= 1) return false; // 1 和小于 1 的数不是素数 if (n == 2 || n == 3) return true; // 2 和 3 是素数 if (n % 2 == 0) return false; // 偶数不是素数 srand(time(0)); // 初始化随机数种子 for (int i = 0; i < iterations; ++i) { unsigned int a = 2 + rand() % (n - 3); // 随机选择 a，使得 2 <= a <= n-2 if (powerMod(a, n - 1, n) != 1) { return false; // 如果不满足费马小定理，则 n 不是素数 } } return true; // 如果所有测试都通过，则认为 n 很可能是素数 } int main() { unsigned int num; cout << "请输入一个 32 位整数进行费马素性测试: "; cin >> num; if (fermatTest(num)) { cout << num << " 很可能是素数." << endl; } else { cout << num << " 不是素数." << endl; } return 0; } ``` #### 代码说明 1. **快速幂取模函数**：`powerMod` 函数实现了快速幂取模算法，用于高效计算 \( a^{b} \mod c \)[^1]。 2. **费马素性测试函数**：`fermatTest` 函数执行多次费马测试，以减少误判的可能性。每次测试中，随机选择一个基数 \( a \)，并检查是否满足 \( a^{n-1} \mod n = 1 \)[^2]。 3. **主函数**：用户输入一个 32 位整数，程序调用 `fermatTest` 函数判断该数是否可能是素数，并输出结果。 #### 注意事项 - 费马素性测试是一种概率性算法，可能会将某些合数误判为素数（称为伪素数）。为了提高准确性，可以通过增加测试次数或结合其他素性测试方法（如米勒-拉宾测试）。 - 该实现仅适用于 32 位无符号整数。对于更大的数，需要考虑更高效的算法和数据类型。