Here's the problem.
A more useful way to phrase it is that there are $n$ rounds, with all bulbs initially switched off before round 1, and on round $r$, bulb $k$ is toggled if $r$ divides $k$. Under this formulation, the number of times bulb $k$ is toggled is exactly the number of factors it has, and for an off bulb to be switched on after $n$ rounds, it has to have been toggled an odd number of times. Thus, we need to identify which numbers in $\{1, 2, \ldots, n\}$ have an odd number of factors.
By the fundamental theorem of arithmetic, any integer $k$ factorises into some product of primes, i.e.
$$k = p_1^{e_1} p_2^{e_2} \cdots p_m^{e_{m}}$$
for some primes $p_i$ is prime and exponents $e_i > 0$. Each factor of $k$ is thus of the form
$$p_1^{e_1'} p_2^{e_2'} \cdots p_m^{e_m'},$$
where $0 \leq e_i' \leq e_i$. Since there are $e_i + 1$ choices for each of these factor exponents $e_i'$, and each choice is independent of the choice of the other exponents, we conclude that $k$ has exactly
$$(e_1 + 1)(e_2 + 1) \cdots (e_m + 1)$$
factors. But this product is odd only when each $(e_i + 1)$ is odd, i.e. when $e_i$ is even, so
$$k = \left(p_1^{e_1 / 2} p_2^{e_2 / 2} \cdots p_m^{e_m / 2}\right)^2.$$
So bulb $k$ is left on after $n$ rounds exactly when $k$ is a perfect square.
Naively, we could implement the algorithm as
int bulbs_on_after_n_rounds(int n) {
int on = 0;
for (int k = 1; k * k <= n; ++k) {
++on;
}
return on;
}but since there are exactly $\lfloor \sqrt{n} \rfloor$ perfect squares in $\{1, 2, \ldots, n\}$, we can also do
int bulbs_on_after_n_rounds(int n) {
return std::sqrt(n);
}The time complexity of the first solution is $O(\sqrt{n})$, and depends on how std::sqrt is implemented for the second solution.
