Question

You are given an integer n. We say that two integers x and y form a prime number pair if:

• 1 <= x <= y <= n
• x + y == n
• x and y are prime numbers

Return the 2D sorted list of prime number pairs [xi, yi]. The list should be sorted in increasing order of xi. If there are no prime number pairs at all, return an empty array.

Note: A prime number is a natural number greater than 1 with only two factors, itself and 1.

Question

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.

Return the number of bulbs that are on after n rounds.

Solution

Each position is only switched on its factor rounds, and factors appear in pairs except when squared, where the factor is the same. Therefore, the problem is equivalent to finding the number of times a perfect square appears.

每个位置只在其因子回合会被切换，除了平方时因子相同，其他时候因子都是成对出现的。因此改题目等价于求平方数出现次数。

Code

1
2
3
4
5
6
7
8
9
10

class Solution {
public:
    int bulbSwitch(int n) {
        // bulbs will switch in factor round
        // since factor round will appear with pair
        // we just need to count square round

        return (int) sqrt(n);
    }
};