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?

You search for factors in increasing order and divide them out. If any is repeated then it can come out from hiding under the square root. — lastchance, May 14 '23 at 16:20
Perhaps this question is better suited at https://math.stackexchange.com/ — Ted Lyngmo, May 14 '23 at 16:23

lastchance · Accepted Answer · 2023-05-14T17:33:25.710

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

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

1 Answers1