Determining if square root is an integer

In my program, I am trying to take the find the largest prime factor of the number 600851475143. I have made one for loop that determines all the factors of that number and stores them in a vector array. The problem I am having is that I don't know how to determine if the factor can be square rooted and give a whole number rather than a decimal. My code so far is:

#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]))                      // ??? 
     }
}

Can someone show me how to determine whether a number can be square rooted or not through my if statement?

---

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

As hobbs pointed out in the comments,

Assuming that double is the usual 64-bit IEEE-754 double-precision float, for values less than 2^53 the difference between one double and the next representable double is less than or equal to 1. Above 2^53, the precision is worse than integer.

So if your int is 32 bits you are safe. If you have to deal with numbers bigger than 2^53, you may have some precision errors.

---

The following should work. It takes advantage of integer truncation.

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

It works because the square root of a non-square number is a decimal. By converting to an integer, you remove the fractional part of the double. Once you square this, it is no longer equal to the original square root.

---

You also have to take into account the round-off error when comparing to cero. You can use std::round if your compiler supports c++11, if not, you can do it yourself (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])  
     }
}

链接地址: http://www.djcxy.com/p/86640.html

上一篇: 装配中的平方根，如何移位和更改位

下一篇: 确定平方根是否为整数