I need to find an efficient way to square longs up to 10^13. I have the following code in Java:

static boolean squarefree(long number) {
        for (int i = 2; i <= number; i  ) {
            if (number % (i*i) == 0) {
                return false;
            }
        }
        return true;
    }

This returns a divide by zero error, yet i is not zero at any point, so I'm not sure why I am getting that error. The reason I did not use Math.pow(i ,2) is because I felt that it would be much slower than just multiplying the number by itself.

Does anyone know why this error is occuring, or how I can efficiently square numbers

CodePudding user response：

You are experiencing an Integer Overflow.

The function below resolves this issue.

    static boolean isSquareFree(long number) {
        long upperLimit = (long) Math.sqrt(number);
        for (long i = 2; i <= upperLimit; i  ) {
            if (number % (i*i) == 0) {
                return false;
            }
        }
        return true;
    }

Algorithm explained

We are trying to determine if a number is squarefree.

The largest integer (i) whose square perfectly divides the number (n) can be expressed as

i = floor(sqrt(n))

For example, 81 = 9^2.
Therefore checking upto upperLimit = (long) Math.sqrt(number) is sufficient.
Now,
Since upperLimit is less than or equal to the square root of number, which fits in the datatype long,
we can rest assured that its square will also fit in type long.

Hence, we won't have any more Integer Overflows.

CodePudding user response：

When your number is greater than Integer.MAX_VALUE then your loop will never quit.

Bad thing is, i will overflow to Integer.MIN_VALUE (Integer.MAX_VALUE 1 == Integer.MIN_VALUE) and from there starts to approach 0 from the negative direction (due to i ).

Once it reaches zero, i * i will still yield 0 and that's why you get that exception.

As mentioned in the comments, changing int i to long i would maybe resolve that problem. When you're starting to work with even bigger numbers, you may have to resort to using BigInteger or some other algorithm.