房间里有100盏电灯，编号为1，2，3……100，每盏灯上有一个按钮，初始时灯全都是关的。编好号的100位同学由房间外依次走进去，将自己编号的倍数的灯的按钮全部按一次，例如第一位同学把编号是1的倍数的灯的按钮按一下（此时100盏灯全亮），第二位同学把编号是2的倍数的灯的按钮按一下（此时只有50盏灯亮着，50盏被这个人按灭了）……第100位同学把编号是100的倍数的灯（即编号为100的灯）的按钮按一下，请问依次走完后，还有多少盏灯亮着？
方法一.通过模拟同学进出场开关灯实现
/**
*100盏灯开关的问题通过模拟同学进出实现
*1为开，0为关
* @author Zodiac
*
*/
public class Demo04 {
public static void main(String[] args) {
// TODO Auto-generated method stub
/*模拟100盏灯，1表示开，0表示关*/
byte light[]=new byte[100];
/*最后灯开着的数量*/
int result=0;
/*将灯初始化为全关*/
for(int i=0;i方法二.通过以上进出场开关流程分析，我们可以通过对灯编号进行约数计数来降低复杂度，约数个数为奇数的灯最后是开着的，约数为偶数的灯是关着的。
/**
*100盏灯开关的问题通过计算约数个数实现
* @author Zodiac
*/
public class Demo05 {
public static void main(String[] args) {
// TODO Auto-generated method stub
/*保存开灯数量*/
int result=0;
/*保存约数个数*/
int num[]=new int[100];
/*将数组初始化为0*/
for(int i=0;i方法三.进一步分析，约数是成对出现的，因此只有完全平方数约数个数为奇数，其他数的约数个数都为偶数，因此本题实际上可以转换为求100内完全平方数的个数。当然答案为10。我们在上面两个代码中将开灯编号打出来，结果如下：
1 4 9 16 25 36 49 64 81 100
10结果验证了求100内完全平方数的个数。
该题，我是永循序渐进的的思想去解决的，可能一开始不能想到将问题转换为求100以内完全平方数的个数，但是通过模拟实现，再一步步抽象分析优化得到了最简单的模型，当然中间过程并不一定要去代码实现，我这里只是为了做比较。因此给我的启发是遇到问题要分步分析去优化。
问题延伸：如果是n盏灯，k个人呢
这里给出复杂度为O(k*n)的约数个数算法，这里的约数个数是指ni在1-k之间的约数个数，方法一复杂度也为O(k*n)。还没想到怎么优化，读者如果有想法，希望给点指点。
代码：
public class Demo05 {
public static void main(String[] args) {
// TODO Auto-generated method stub
Light light=new Light(10,5);
light.calculate();
System.out.println("Number of Lights that are open:\t"+light.getResult());
Light light2=new Light(100,100);
light2.calculate();
System.out.println("Number of Lights that are open:\t"+light2.getResult());
}
}
class Light{
private int lightNum; //灯数
private int personNum; //人数
private int result=0; //保存开灯数量
/**
* @param lightNum
* @param personNum
*/
public Light(int lightNum, int personNum) {
this.lightNum = lightNum;
this.personNum = personNum;
}
/*返回开灯数*/
public int getResult(){
return this.result;
}
public void calculate(){
/*保存约数个数*/
int num[]=new int[this.lightNum];
/*将数组初始化为0*/
for(int i=0;i结果：
Lights that are open:1 4 6 7 8 10
Number of Lights that are open: 6
Lights that are open:1 4 9 16 25 36 49 64 81 100
Number of Lights that are open: 10