Question: 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.

[![error](https://i.stack.imgur.com/FBiFy.png)](https://i.stack.imgur.com/FBiFy.png)

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

Answer: 
You are experiencing an [Integer Overflow](https://en.wikipedia.org/wiki/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](https://en.wikipedia.org/wiki/Square-free_integer).

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 Overflow](https://en.wikipedia.org/wiki/Integer_overflow)s.
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.