首页 文章

确定平方根是否为整数

提问于
浏览 次
3

在我的程序中，我试图找到数字600851475143的最大素数因子 . 我已经制作了一个for循环，它确定了该数字的所有因子并将它们存储在向量数组中 . 我遇到的问题是我不知道如何确定因子是否可以是平方根并且给出整数而不是小数 . 到目前为止我的代码是：

#include <iostream>
#include <vector>
#include <math.h>

using namespace std;
vector <int> factors;

int main()
{
    double num = 600851475143;
    for (int i=1; i<=num; i++)
    {
        if (fmod(num,i)==0)
        {
            factors.push_back(i);
        }
    }

     for (int i=0; i<factors.size(); i++)
     {
         if (sqrt(factor[i]))                      // ??? 
     }
}

有人可以通过我的if语句告诉我如何确定一个数字是否可以平方根？

c++ arrays loops math sqrt

6 回答

  • 3
    int s = sqrt(factor[i]);
if ((s * s) == factor[i])

    正如霍布斯在评论中指出的那样，

    假设double是通常的64位IEEE-754双精度浮点数，对于小于2 ^ 53的值，一个double和下一个可表示的double之间的差值小于或等于1.高于2 ^ 53，精度比整数差 .

    因此，如果您的int是32位，那么您是安全的 . 如果您必须处理大于2 ^ 53的数字，则可能会出现一些精度错误 .

    回复于
  • 2

    完美的正方形只能在基数16中以0,1,4或9结束 . 因此，对于75％的输入（假设它们是均匀分布的），您可以避免调用平方根来换取一些非常快速的比特 .

    int isPerfectSquare(int n)
{
    int h = n & 0xF;  // h is the last hex "digit"
    if (h > 9)
        return 0;
    // Use lazy evaluation to jump out of the if statement as soon as possible
    if (h != 2 && h != 3 && h != 5 && h != 6 && h != 7 && h != 8)
    {
        int t = (int) floor( sqrt((double) n) + 0.5 );
        return t*t == n;
    }
    return 0;
}

    用法：

    for ( int i = 0; i < factors.size(); i++) {
   if ( isPerfectSquare( factor[ i]))
     //...
}

    Fastest way to determine if an integer's square root is an integer

    回复于
  • 0

    以下应该有效 . 它利用整数截断 .

    if (int (sqrt(factor[i])) * int (sqrt(factor[i])) == factor[i])

    它的工作原理是因为非方数的平方根是小数 . 通过转换为整数，可以删除double的小数部分 . 一旦你对它进行平方，它就不再等于原始的平方根 .

    回复于
  • 10

    与cero比较时，您还必须考虑舍入误差 . 如果编译器支持c 11，你可以使用std :: round，如果没有，你可以自己动手（here）

    #include <iostream>
#include <vector>
#include <math.h>

using namespace std;
vector <int> factors;

int main()
{
    double num = 600851475143;
    for (int i=1; i<=num; i++)
    {
        if (round(fmod(num,i))==0)
        {
            factors.push_back(i);
        }
    }

     for (int i=0; i<factors.size(); i++)
     {
         int s = sqrt(factor[i]);
         if ((s * s) == factor[i])  
     }
}
    回复于
  • 3

    你问的是错误的问题 . 你的算法错了 . （好吧，并非完全如此，但如果要按照提出的想法进行纠正，那将是非常低效的 . ）使用您的方法，您还需要递归地检查立方体，第五权力和所有其他主要权力 . 例如，尝试找到5120 = 5 * 2 ^ 10的所有因子 .

    更容易的方法是通过划分找到它后删除一个因子

    num=num/i

    如果它不再是一个因素，只会增加i . 然后，如果迭代遇到一些i = j ^ 2或i = j ^ 3，...，则所有因子j（如果有的话）在早期阶段已经被删除，当时我有值j，并且在因子数组 .

    你也可以提到这是来自 Euler project, problem 3 . 那么你可能会发现最近的讨论“advice on how to make my algorithm faster”，其中讨论了更有效的分解算法变体 .

    回复于
  • 0

    这是我写的一个简单的C函数，用于确定数字是否具有整数平方根：

    bool has_sqrtroot(int n)
{
    double sqrtroot=sqrt(n);
    double flr=floor(sqrtroot);
    if(abs(sqrtroot - flr) <= 1e-9)
        return true;

    return false;
}
    回复于

相关问题