5

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?

4pie0
  • 29,204
  • 9
  • 82
  • 118
user3344400
  • 69
  • 1
  • 1
  • 3
  • possible duplicate of [Fastest way to determine if an integer's square root is an integer](http://stackoverflow.com/questions/295579/fastest-way-to-determine-if-an-integers-square-root-is-an-integer) – 4pie0 Mar 07 '14 at 00:37
  • The problem is Euler project no. 3, last discussed here: http://stackoverflow.com/q/22153481/3088138 – Lutz Lehmann Mar 07 '14 at 11:16

7 Answers7

16
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.

davir
  • 912
  • 5
  • 7
  • 1
    Yep. This should work for `factor[i]` up to 2^53 or so. – hobbs Mar 07 '14 at 00:34
  • Yes, and since factor is a vector of int's, we're safe. – davir Mar 07 '14 at 00:36
  • Well `int` could be 64-bit for all we know. :) – hobbs Mar 07 '14 at 00:38
  • But then I suppose your 2^53 limit would be raised too. Where did you get it, btw? – davir Mar 07 '14 at 00:38
  • 1
    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. – hobbs Mar 07 '14 at 00:40
  • (Because there is 1 sign bit, 11 exponent bits, and 52 (plus one hidden) mantissa bits) – hobbs Mar 07 '14 at 00:42
  • @hobbs I'm still not 100% convinced that this would affect the result in this particular case, but you are right. I'll add this to the answer. – davir Mar 07 '14 at 00:43
3

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.

Dead
  • 232
  • 1
  • 10
  • 1
    I don't think "decimal" is the right word, since we're not talking about strings. – Kerrek SB Mar 07 '14 at 00:52
  • Thanks. Although decimal portion made sense, it wasn't the correct way of saying it. I had to look up what the numbers before and after the decimal place were called. Apparently one of the accepted methods is fractional part. Found the answer [here](http://math.stackexchange.com/questions/64042/what-are-the-numbers-before-and-after-the-decimal-point-referred-to-in-mathemati). – Dead Mar 07 '14 at 01:05
3

Perfect squares can only end in 0, 1, 4, or 9 in base 16, So for 75% of your inputs (assuming they are uniformly distributed) you can avoid a call to the square root in exchange for some very fast bit twiddling.

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;
}

usage:

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

Community
  • 1
  • 1
4pie0
  • 29,204
  • 9
  • 82
  • 118
2

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])  
     }
}
Community
  • 1
  • 1
sebas
  • 869
  • 7
  • 16
0

You are asking the wrong question. Your algorithm is wrong. (Well, not entirely, but if it were to be corrected following the presented idea, it would be quite inefficient.) With your approach, you need also to check for cubes, fifth powers and all other prime powers, recursively. Try to find all factors of 5120=5*2^10 for example.

The much easier way is to remove a factor after it was found by dividing 

num=num/i

and only increase i if it is no longer a factor. Then, if the iteration encounters some i=j^2 or i=j^3,... , all factors j, if any, were already removed at an earlier stage, when i had the value j, and accounted for in the factor array.

You could also have mentioned that this is from the Euler project, problem 3. Then you would have, possibly, found the recent discussion "advice on how to make my algorithm faster" where more efficient variants of the factorization algorithm were discussed.

Community
  • 1
  • 1
Lutz Lehmann
  • 25,219
  • 2
  • 22
  • 51
0

Here is a simple C++ function I wrote for determining whether a number has an integer square root or not:

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

    return false;
}
wp78de
  • 18,207
  • 7
  • 43
  • 71
Anagheem
  • 1
0

As sqrt() function works with floating-point it is better to avoid working with its return value (floating-point calculation occasionally gives the wrong result, because of precision error). Rather you can write a function- isSquareNumber(int n), which will decide if the number is a square number or not and the whole calculation will be done in integer.

bool isSquareNumber(int n){
    int l=1, h=n;
    while(l<=h){
        int m = (l+h) / 2;
        if(m*m == n){
            return true;
        }else if(m*m > n){
            h = m-1;
        }else{
            l = m+1;
        }
    }
    return false;
}

int main()
{
   // ......
     for (int i=0; i<factors.size(); i++){
         if (isSquareNumber(factor[i]) == true){
              /// code
         }
     }
}
Mahedi Kamal
  • 179
  • 1
  • 9