如何从平方根符号下分解出完全正方形？

Question

我正在尝试计算平方根，并保留不能在C++中变为整数的部分，我在Stack Overflow上找到这篇文章，但它仍然会有小数。 例如，如果我想计算

√8

，我希望结果是

2√2

而不是

2.828

。我也找到了这篇文章，但是它只会判断它是否是一个整数，而不是解决它。

起初，我试图将每个不能变成整数的数字都保留完整，并使用while循环来实现，但我发现这样做几乎是不可能的，因为数字(2,3, 5、7、10、13、17、19、23、27...）。当我在

Microsoft Math Solver

中输入√573818832时，它可以告诉我这个数字等于

12√3984853

，我想知道它是如何解决这个问题的。

有什么方法可以改进我的第一个方法吗？

Answer 1

令 sqrt(n) = a * sqrt( b ) = sqrt( a² * b )

按升序搜索因素。一种类似筛子的方法是可能的，但是，为了简单起见，现在就用蛮力来做。您基本上是在寻找重复的因素（上面的 a²），因此，如果您找到一个因素（使用 % 运算符），请检查该因素是否再次出现。如果它是一个重复的因素，它进入 a，否则进入 b.

#include <iostream>
using namespace std;

using INT = unsigned long long;

void surd( INT n, INT &a, INT& b )     // write n as a*sqrt( b );
{
   a = b = 1;
   INT i = 2;
   while( i * i <= n )          // seek repeated factors
   {
      if ( n % i == 0 )         // i is a factor
      {
         n /= i;
         if ( n % i == 0 )      // i is a repeated factor
         {
            n /= i;
            a *= i;
         }
         else                   // i is not a repeated factor
         {
            b *= i;
         }
      }
      else
      {
         i++;
      }
   }
   b *= n;                      // what's left over stays inside the square root
}


int main()
{
   INT n, a, b;
   cout << "Enter n: ";   cin >> n;
   surd( n, a, b );
   cout << "sqrt( " << n << " ) = " << a;
   if ( b != 1 ) cout << " * sqrt( " << b << ")\n";
}

举个例子：

Enter n: 573818832
sqrt( 573818832 ) = 12 * sqrt( 3984853)

和

Enter n: 152399025
sqrt( 152399025 ) = 12345