2015-01-20
问题
**问题1、**房间里有100盏电灯，编号为1, 2, ..., 100，每盏灯上有一个按钮，初始时灯全都是关的。有80个同学依次编号为1, 2,..., 80，这些同学依次进入房间，将自己编号的倍数的灯的按钮全部按一次，例如第一位同学（编号是1）把编号是1的倍数的灯的按钮按一下（此时100盏灯全亮），第二位同学（编号是2）把编号是2的倍数的灯的按钮按一下（此时只有50盏灯亮着，50盏被这个人按灭了），……，第80位同学把编号是80的倍数的灯（即编号为80的灯）的按钮按一下，请问依次走完后，还有多少盏灯亮着？
**问题2、**如何求一个正整数的约数的个数？（本文的约数是正约数）
**问题3、**如何找一个约束个数为100的数字？
答案
问题1：
（转换思路，找出规律） 被按奇数次的灯在最后会亮着，而偶数次的等是灭的。这就转换成了数字的约数的个数问题。
例如，要判断编号为9的灯在最后是亮还是灭，先求9的小于等于80的所有约数的个数（约数有1，3，9，共3个约数，也意味着编号为1、3、9的同学会按9号灯的按钮）。约数个数为奇数，故9号灯是亮的。
既然，这样如何求约数的个数？
问题2：
要求整数N的约数的个数，最简洁的思路是求出其所有的约数并计数。
若N%i==0，那么i就是N的一个约数。
思路一：遍历1...N的所有整数，判断每一个数字是否是N的约数，并计数。
思路二：设n=floor(sqrt(N))，遍历1...n的所有整数，判断每一个数字是否是N的约数，并计数，得到count，若n×n = N，那么N的约数个数为count×2-1，否则为count×2。
思路三：也可以用数学上的方法来解决。首先分解质因数，再结合约数个数定理解决。
问题3：
用约数个数定理解决。
更机智的解决方法
被按奇数次的灯在最后会亮着，而偶数次的等是灭的。所以只要判断编号为n的灯的约数是奇数个还是偶数个即可。
令k=(int)sqrt(n)，若k×k == n，那么编号为n的灯的约数是奇数个。于是，很容易判断，9的约数是奇数个（1、3、9），10的约数是偶数个（1、10、2、5）。
参考
http://www.blogjava.net/amigoxie/archive/2012/10/18/389818.html
http://www.cnblogs.com/yinger/archive/2012/08/14/2639097.html