如何从平方根符号下方分解出完全平方数?

huangapple go评论90阅读模式
英文:

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

问题

I am trying to calculate the square root, and keep the part which could not change into an integer in C++, and I found This post on Stack Overflow, but it will still have a 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 it's an integer, but not solving it.
At first, I tried to keep each number that could not be changed into an integer completely, and using a 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 type √573818832 into Microsoft Math Solver, it could show me that the number is equal to 12√3984853, and I wonder how it could solve the problem.
Is there any way to improve my first method?

英文:

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?

答案1

得分: 3

让 sqrt(n) = a * sqrt( b ) = sqrt( a<sup>2</sup> * b )

按递增顺序搜索因子。可以使用类似筛选的方法,但为简单起见,现在只通过蛮力来做。基本上,您正在寻找重复的因子(上面的 a<sup>2</sup>),因此,如果找到一个因子(使用 % 运算符),请检查该因子是否再次出现。如果它是一个重复的因子,它将放在 a 中,否则放在 b 中。

#include <iostream>
using namespace std;

using INT = unsigned long long;

void surd( INT n, INT &a, INT& b )     // 将 n 写成 a*sqrt( b );
{
   a = b = 1;
   INT i = 2;
   while( i * i <= n )          // 寻找重复的因子
   {
      if ( n % i == 0 )         // i 是一个因子
      {
         n /= i;
         if ( n % i == 0 )      // i 是一个重复的因子
         {
            n /= i;
            a *= i;
         }
         else                   // i 不是一个重复的因子
         {
            b *= i;
         }
      }
      else
      {
         i++;
      }
   }
   b *= n;                      // 剩下的部分留在平方根内
}


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

示例:

输入 n: 573818832
sqrt( 573818832 ) = 12 * sqrt( 3984853)

和

输入 n: 152399025
sqrt( 152399025 ) = 12345
英文:

Let sqrt(n) = a * sqrt( b ) = sqrt( a<sup>2</sup> * 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<sup>2</sup> 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 &lt;iostream&gt;
using namespace std;

using INT = unsigned long long;

void surd( INT n, INT &amp;a, INT&amp; b )     // write n as a*sqrt( b );
{
   a = b = 1;
   INT i = 2;
   while( i * i &lt;= 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&#39;s left over stays inside the square root
}


int main()
{
   INT n, a, b;
   cout &lt;&lt; &quot;Enter n: &quot;;   cin &gt;&gt; n;
   surd( n, a, b );
   cout &lt;&lt; &quot;sqrt( &quot; &lt;&lt; n &lt;&lt; &quot; ) = &quot; &lt;&lt; a;
   if ( b != 1 ) cout &lt;&lt; &quot; * sqrt( &quot; &lt;&lt; b &lt;&lt; &quot;)\n&quot;;
}

As examples:

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

and

Enter n: 152399025
sqrt( 152399025 ) = 12345

huangapple
  • 本文由 发表于 2023年5月15日 00:12:19
  • 转载请务必保留本文链接:https://go.coder-hub.com/76248478.html
匿名

发表评论

匿名网友

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

确定