Tricky interview puzzle

You have this code in Javascript (even though language choice does not matter):

var arr = new Array(101);
for (skip = 1; skip <= 100; skip++) {
    for (i = 0; i <= 100; i+= skip) {
        arr[i] = !arr[i];
    }
}

Obviously, after this code is run, there will be bunch of true and false values in the array. If arr[i] was touched even number of times, it will be false, otherwise it will be true.

The question is what pattern do these value form? Can you quickly tell whether arr[15] will be true of false? What about arr[81]?

I know the answer (arr[x] will be true when x is a square of some integer number), but what I don't understand is how am I supposed to come up with it quickly during the interview?

The bonus question is what is time complexity of this piece of code, assuming you do it for N array elements (I will answer it below)?