将一个整数拆分成两个整数的平方和算法

YuHuang.Neil

问题：请使用C/C++写一个程序实现将一个整数拆分成两个整数的平方和，把所有的可能的组合都要计算出来。

答：假定输入的整数为n，则扫描1-(n的平方根)之间的整数，令row=1，column＝(int)(sqrt((double)given)+0.5)，使得row*row+column*column=n的数输出即可。

代码如下所示：

////  main.cpp//  MyProjectForCPP////  Created by labuser on 11/2/11.//  Copyright 2011 __MyCompanyName__. All rights reserved.//#include <iostream>#include <math.h>using namespace std;int main (int argc, const char * argv[]){    int given;    int row,column;    int count;    char line[100];        printf("\nRepressenting a Given Number as the the Sum of Two Squares");    printf("\n==========================================================\n");    printf("\nAn Integer Please ---> ");    gets(line);        given = atoi(line);    printf("\nCount     X       Y");    printf("\n------  -----  ------");        row =1;    column=(int)(sqrt((double)given)+0.5);    while (row<=given && column>0) {        if(row*row+column*column==given){            ++count;            printf("\n%5d%7d%7d",count,row,column);            ++row;            --column;        }        else if(row*row+column*column>given)        {            --column;        }else{            ++row;        }    }        if(count==0){        printf("\n\nSorry, NO ANSWER found.");    }else{        printf("\n\nThere are %d possible answers.\n",count);    }        return 0;}

运行结果：
Repressenting a Given Number as the the Sum of Two Squares
==================================================
An Integer Please ---> 200

Count     X       Y
------  -----  ------
    1      2     14
    2     10     10
    3     14      2

There are 3 possible answers.