What is the best solution for the 'Students and Lockers' problem?

Question

I thought that it would be fun to present some classic CS problems and let people show their algorithm optimization skills. The hope is that we get to see some clever techniques to solve abstract problems that we may be able to implement in practice.

Ideally solutions would be presented in pseudo code with a big O classification. Proof of that classification is gravy. On to the problem:

There are N closed lockers and N students present. The first student opens each locker. The second student opens or closes every second locker. This continues where the nth student opens and closes every nth locker. After N students what lockers are open? How many lockers are open?

Answer 1

Students will only flip the state of those lockers that their number is a divisor of (student 2 flips the even lockers, student 3 flips the lockers divisible by 3, so on and so forth...). So, the only lockers that will remain open after N rounds are those that have an odd number of divisors (because they start closed, an odd number of flips will leave it open). The only numbers that have an odd number of divisors are perfect squares, so all of the perfect-square-numbered lockers will be left open. So after N rounds, the number of lockers left open will be the square root (floored) of N.

This solution would be O(sqrt(N)) to know exactly which lockers are open, but O(1) if you only need to know how many lockers are open.