A very big building in which thousand monkeys are living is lighted by thousand lamps. Every lamp is connected to a unique on/off switch, which are numbered from 1 to 1000. At some moment, all lamps are switched off. But because it is becoming darker, the monkeys would like to switch on the lights. They will do this in the following way.

Monkey 1 presses all switches that are a multiple of 1.
Monkey 2 presses all switches that are a multiple of 2.
Monkey 3 presses all switches that are a multiple of 3.
Monkey 4 presses all switches that are a multiple of 4.
Etc., etc.

How many lamps are switched on after monkey 1000 pressed his switches? And which lamps are switched on?

If the first monkey has done his job, lamp 1, 2, 3, ... and 1000 are on.
If the second monkey has done his job, lamp 1, 3, 5.. and 999 are on.
enz.

Let us figure out the state of lamp number 10 after all monkeys have pressed their buttons. 10 = 2 * 5, 10 = 5 * 2, 10 = 10 * 1 and 10 = 1 * 10. So 10 is a multiple of 1, 2, 5 and 10. Hence monkey 1, monkey 2, monkey 5 and monkey 10 have pressed on switch 10. This implies that lamp 10 is switched of when all monkeys have pressed their buttons.

Now take a lamp number x. Of course it holds that x = 1 * x and x = x * 1. x is always a multiple of 1 and of x. If x is a prime, then there are other possibilities anymore, which implies that the lamp is switched of in the end. If x is not a prime there is at least one way in which we can write x = n * m, where n and m are integers. So x is a multiple of n and of m, hence monkey n and monkey m press button x. If x is not a square, x has an even number of different multiples. Then x will be switched of in the end. But if x is a square, x = n * n, in other words x = 1, 4, 9, ... then x has an odd number of multiples. That implies that if x is a square, lamp x will be swichted on in the end.

Since 31*31=961 and 32*32 = 1024 there are 31 different squares below 1000. Hence 31 lamps are switched on in the end, these are 1, 4, 9, 16, 25, ... and 961.