英文:
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 <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
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库,让每个人都能够通过互相帮助和分享经验来进步。
评论