费马质数分解c++代码
时间: 2023-09-24 14:06:03 浏览: 54
以下是一个简单的费马质因数分解的 C++ 代码:
```cpp
#include <iostream>
#include <cmath>
using namespace std;
long long FermatFactorization(long long n) {
long long a = ceil(sqrt(n));
long long b2 = a * a - n;
while (!is_square(b2)) {
a++;
b2 = a * a - n;
}
return a - sqrt(b2);
}
bool is_square(long long n) {
long long root = sqrt(n);
return root * root == n;
}
int main() {
long long n = 8051; // 要分解的数
cout << "原数:" << n << endl;
long long p = FermatFactorization(n);
cout << "分解结果:" << p << " x " << n / p << endl;
return 0;
}
```
解释一下代码:
- 函数 `FermatFactorization` 输入一个整数 `n`,返回 `n` 的一个因子 `p`(其中 `p` 是一个质数)。
- 函数 `is_square` 输入一个整数 `n`,判断 `n` 是否是某个整数的平方。
- 在 `main` 函数中,我们先输入要分解的数 `n`。然后调用 `FermatFactorization` 函数得到一个因子 `p`,另一个因子就是 `n / p`。最后输出结果。
需要注意的是,这个算法只能分解比较小的整数,对于很大的整数,需要使用更加高效的算法。