C# 算法题

Question

求两个自然数，其和是667，最小公倍数与最大公约数之比是120：1。（例如：115，552）-------------------------------------------------------------我得出的答案是115，552，232，435。但是觉得自己的算法很繁琐，没有效率。请问各位有简单一点的算法算这到题吗？

Answer 1

//至少你要把你的算法帖出来，否则我都不知道有没有你的精简int 最大公约数(int 大数, int 小数)
{
    if (小数 == 0) return 大数;
    else return (最大公约数(小数, 大数 % 小数));
}int 最小公倍数(int 大数, int 小数)
{
    return 大数 * 小数 / 最大公约数(大数, 小数);
}private void button2_Click(object sender, EventArgs e)
{
    int Sum = 667;    for (int a = 1; a <= Sum / 2; a++)
    {
        int b = Sum - a;
        if (最小公倍数(a, b) / 最大公约数(b, a) == 120 / 1)
            MessageBox.Show(string.Format("{0},{1}", a, b));
    }
}

Answer 2

int 最大公约数(int 大数, int 小数)
{
    if (小数 == 0) return 大数;
    else return (最大公约数(小数, 大数 % 小数));
}
private void button2_Click(object sender, EventArgs e)
{
    int Sum = 667;    for (int a = 1; a <= Sum / 2; a++)
    {
        int b = Sum - a;
        int c = 最大公约数(b, a);
        if ((a * b) / (c * c) == 120 / 1)
            MessageBox.Show(string.Format("{0},{1}", a, b));
    }
}//最后精简成这样，通过数学公式省掉最小公倍数方法

Answer 3

设最大公约数为x, 则最小公倍数是120x. 那么两数的积为120x^2,又已知两数的和为667设其中一个数为ax,则另外一个数为(120x/a)ax+(120x/a) = 667
a + 120/a = 667/x667进行因数分解得到x只能是 1,23,29其中一个.循环3次: 
1:  1+120/a = 667   无解
23: a +120/a = 29   a = 5
29: a + 120/a = 23  a = 8然后代入a计算得到上面楼主的结果.

Answer 4

//目前代码写成这样，循环20次得到结果
//请syeerzy、shrinerain看看有什么地方可以再次优化？
int Sum = 667;
int Quo = 120;for (int i = 2; i < Math.Sqrt(Sum); i += 2)
{
    if (Sum % i == 0)
    {
        for (int j = 2; j < Math.Sqrt(Quo); j++)
        {
            if (Quo % j == 0)
            { 
                int x = i;
                int a = j;
                if ((a * x + (Quo * x / a) == Sum) &&
                    (a + Quo / a == Sum / x))
                    MessageBox.Show(string.Format("{0},{1}", a * x, Quo * x / a));
                x = Sum / i;
                if ((a * x + (Quo * x / a) == Sum) &&
                    (a + Quo / a == Sum / x))
                    MessageBox.Show(string.Format("{0},{1}", a * x, Quo * x / a));
            }
            if (j == 2) j++;
        }
    }
    if (i == 2) i++;
}

Answer 5

zswang(伴水清清)Math.Sqrt(Sum)  和  Math.Sqrt(Qum)
为什么要把范围设定在平方根之内，超越了平方根一样会有Sum，Qum的质因数，是吗？ ---------------------------------------------------------------------------a * x + (Quo * x / a) == Sum  和  a + Quo / a == Sum / x这两条表达式不是一样的吗，为什么要写2个？我好多不懂啊-_-！

Answer 6

相隔太久了///这是分解的两个乘积因子
int x = i; // No.1
//。。
x = Sum / i; //No.2所以x不会大于Sqrt(Sum)

Answer 7

i和(Sum / i)是667的所有质因数的范围。
...
i * (Sum / i) = Sum

Answer 8

I see！Thanks you very much！！太高兴了！^-^

Answer 9

   public static int text3(int n,int m)//最大公约数
        {
            if (n > m)
            {
               return text3(n-m,m);
            }
            else if (m > n)
            {
                return text3(n, m - n);
            }
            else
            {
                return n;
            }