问素数algo

EN

最简单的方法是从输入数字X的0到平方根运行一个循环，对于每个循环检查sqrt(X ^2)是否为整数。如果存在整数，则返回true，否则返回false。

#include <math.h>      
#include<iostream>   
using namespace std;
int main () {
    int n;
    cin >> n;

    for (int i = 0; i < sqrt(n); i++) {

        if(floor(sqrt(n - i*i))==ceil(sqrt(n - i*i))){
            cout << "true " << i << "^2 + " << sqrt(n - i*i) << "^2 = " << n << endl;    
            return 0;
        } else {
            continue;
        }
    }
    cout << " Cant find two integers satifield a^2 + b^2 = n^2\n";
    return 0;
}

这个算法很简单，但是随着输入的增加，运行起来似乎需要时间。

你没有代码，所以我会告诉你面试官对你的期望：

只在你指出P和Q是任何整数的注释中，这应该是问题的一部分，如果不是，您应该与interviewer

• you确认P和Q是无符号整数，因为平方，而且P和Q不应该大于sqrt(X)

• ，您应该能够通过蛮力搜索从0 t sqrt(X)找到P，q的答案，并检查所有combinations

• you也可以从它生成一个动态规划问题，即列出从0到层的所有数字(sqrt(X))，然后把他们的正方形放进一个数组里。然后，制定一个算法从数组中搜索两个元素的和，等于X

。

有一个定理，叫做两个平方定理之和，它说：

，一个大于1的整数可以写成两个平方的和当且仅当它的素数分解不包含升到奇数幂的3模4的素数同余。

也许你应该知道这件事。

这种检查是可行的。它需要分解X，这是一个众所周知的困难问题，但它只适合于较大的数字。如果X是一个64位数，那么您可以很容易地使用Pollard的Rho算法对其进行因子分析，这并不是很复杂。