Determining if square root is an integer

user3344400 picture user3344400 · Mar 7, 2014 · Viewed 10k times · Source

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?

Answer

davir picture davir · Mar 7, 2014
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.