Bulb Switcher

Problem:

There are n bulbs that are initially off. You first turn on all the bulbs. Then, you turn off every second bulb. On the third round, you toggle every third bulb (turning on if it's off or turning off if it's on). For the ith round, you toggle every i bulb. For the nth round, you only toggle the last bulb. Find how many bulbs are on
after n rounds.

Before we take a jump to the solution, let's first try to clear out what exactly the problem is talking about:

• every i-th distance you switch the bulb to the opposite state (from on to off, or from off to on); actually suppose the bulbs are labelled from 1 to n then the every second bulb will mean that 2, 4, 6, 8, ... all even numbers less than n; while every third bulb will be 3, 6, 9, 12, ... all multiples of 3 that is less than n and so on;
  since the bulb will only have two different states - on or off, the result will be quite clear now; odd switching operations will result in bulb-on state (original state is bulb-off) while even switching operations will give us bulb-off state;

Now the purpose here is clear searching for the odd-operation numbers:

• as for primes, they only have 1 and itself as their factors; so primes are even-operation numbers;
• as for non-primes, normally they will have different pairs of factors like 12 whose factors are 112, 26, 3*4 - 6 different factors, so they are also even-operation numbers;
• but among non-primes, there are some special numbers which are square numbers like 9 whose factors are 19, 33 - three different factors which means we finally got odd-operation numbers!

So that's all we need to know to hack this problem now. But how to get the amount of squares that are less than n, quite simple, right? sqrt(n) is the answer. Confused? ok, all square numbers that is less than n will be 1, 4, 9 ... n and corresponding root will be 1, 2, 3,... sqrt(n) Get it?
Bang. End of story.

• Space cost O(1)
• Time cost O(1)

//AC - 0ms; int bulbSwitch(int n){ return sqrt(n); }