本文介绍一些和因数有关的问题
问题一 出列问题
255个人排一队，进行多次出列操作。每次在当前队列的奇数位的人出列，偶数位的人留在队列中。问最后剩下的人是谁？
分析：
第一次出列，1，3，5，...，255号出列，剩下2，4，6，...，254号留在队列中
第二次出列，2（1*2），6（3*2），10（5*2），...，254（127*2）号出列，剩下4，8，12，...，252号留在队列中
容易发现，不用出列的人的通项公式是 k * 2n号, k = 1,2,3,4,...
因此，当只剩下最后一个人，也就告诉我们 k=1了（如果k还能取2，3，...，说明还有不止一个人留在队列中），那么有 2n <= 256 并且 2* 2n > 256，解得n = 7，所以128号最终留在队中
从结果反过来理解，因数越多，活得越久。正因为128=27，是21，22，...，27的倍数，第一次留下21的倍数，第二次留下22的倍数，...所以每一次它都能够留在队中，直到只剩它自己
问题2 开关灯问题
这是leetcode上的一个问题：灯泡开关
，问题描述如下：
初始时有 n 个灯泡关闭。
第 1 轮，打开所有的灯泡（也就是每1个切换一次开关）。
第 2 轮，每两个灯泡关闭一次（每2个切换一次开关）。
第 3 轮，每三个灯泡切换一次开关（每3个切换一次开关）。
第 i 轮，每 i 个灯泡切换一次开关。
对于第 n 轮，显然只切换最后一个灯泡的开关。
找出 n 轮后有多少个亮着的灯泡
示例:
输入: 3
输出: 1
解释:
初始时, 灯泡状态 [关闭, 关闭, 关闭].
第一轮后, 灯泡状态 [开启, 开启, 开启].
第二轮后, 灯泡状态 [开启, 关闭, 开启].
第三轮后, 灯泡状态 [开启, 关闭, 关闭].
你应该返回 1，因为只有一个灯泡还亮着
分析：
像这种开关的问题一般都是有潜在规律的。对于灯泡j，假设它是a, b的倍数，那么它在第a轮和第b轮都要切换一次开关，操作互相抵消。因此，我们的关注点是，一个数有偶数个还是奇数个因数——有偶数个因数，保持初始灭灯状态；有奇数个因数，则会亮灯
那么什么数会有奇数个因子呢？—— 平方数。因为平方数 = 平方根 * 平方根
一开始我对每一个数都进行判断，判断它是不是平方数。这样，对于n个灯泡规模的问题，时间复杂度为O(n)。当n为9999999时，程序超时了。
于是，尝试优化。实际上，我们不用一个数一个数去判断这个数是不是平方数，我们可以直接找到完全平方数，这是相当容易的，时间复杂度为O(n0.5)
代码实现：
class Solution(object):
def bulbSwitch(self, n):
"""
:type n: int
:rtype: int
"""
# 思路：对于每一个灯泡，找到它所有的因数个数，奇数个则为开启，偶数个则为关闭
light = 0
# for index in range(1, n+1):
# # 如果是平方数，那么肯定有奇数个因数，灯亮；否则有偶数个因数
# # 所以也就是找N以内的平方数个数
# if index**0.5 == int(index**0.5):
# light += 1
# return light
i = 1
while i*i <= n:
i += 1
light += 1
return light
问题3 求给定区间内的素数
问题链接：如何求给定区间内的素数
上面这篇推送中的方法我理解为自底向上法求素数：
从第一个素数2出发，标记后面能被它整除的数。然后移到下一个数，继续标记后面能被它整除的数。在如果遇到一个数，它没有被标记，说明它不能被它之前的（也就是小于它的）任意整数整除(不考虑1)，那么它就是素数
ps：其实这个问题的解法和点灯问题的题干操作方法很像，只不过是把开灯关灯变成了打标记。这样一来，被标记的数一定能被前面的数整除，没被标记的数就是素数
