How to factor out perfect squares from under the square root sign?

Question

I am trying to calculate the square root, and keep the part which could not change into integer in C++, and I found This post on Stack Overflow, but it will still have decimal. For example, if I want to calculate √8, I want the result to be 2√2 but not 2.828. I also found This post, but it will only determine if its an integer, but not solving it.

At first, I tried to keep each number that could not be changed into integer completely, and using while loop to achieve that, but I found that it is almost impossible to do that, because there are too many numbers(2,3,5,7,10,13,17,19,23,27...). When I typing √573818832 into Microsoft Math Solver, it could show me that the number is equal to 12√3984853, and I wonder how could it solve the problem.

Is there are any ways to improve my first method?

Answer 1

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

Search for factors in increasing order. A sieve-like method is possible, but, for simplicity, just do so by brute force for now. You are basically looking for repeated factors (the a² in the above) so, if you find a factor (use the % operator), check whether that factor occurs again. If it's a repeated factor it goes in a, otherwise in 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";
}

As examples:

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

and

Enter n: 152399025
sqrt( 152399025 ) = 12345