大厅里有100盏灯，每盏灯都编了号码，分别为1-100。每盏灯由一个开关来控制。（开关按一下，灯亮，再按一下灯灭。开关的编号与被控制的灯相同。）开始时，灯是全灭的。现在按照以下规则按动开关。第一次，将所有的灯点亮。第二次，将所有2的倍数的开关按一下。第三次，将所有3的倍数的开关按一下。以此类推。第N次，将所有N的倍数的开关按一下。问第100次按完以后，大厅里还有几盏灯是亮的。
网上找了一下，此题还有其他的表述方式类似：礼堂里有100盏电灯,编号1－100,每盏灯由一根灯绳控制,拉一下改变状态.开始灯全是灭的,100个同学依次进入礼堂,
第一个学生把1的倍数的灯绳拉一下,灯全亮；
接着第二个同学把2倍数的灯绳拉一下；
第三个同学把3倍数的灯绳拉一下······第100个学生把100的倍数的灯绳拉一下.最后,礼堂里哪些灯是亮的
1，暴力解法：
暴力解法一般是思路上最接近题意的，按题目要求的步骤直接求解，暴力求解一般计算量也是最大的。
我一般都是先用笨办法计算出结果，再想办法优化。现给出C#暴力解法，得出最后的结果，代码如下：
1classProgram{23//100盏灯，默认全是关着的4staticbool[]lights=newbool[100];56staticvoidMain(string[]args){7//100次开关测试8for(inti=1;i<=100;i++){9ChangeState(i);10}1112//开关完成，打印最后的结果13Console.WriteLine("最后亮灯的还有{0}盏。",lights.Count(r=>r));1415//分别打印每盏灯16for(inti=0;i<100;i++){17if(lights[i]){18Console.WriteLine(i+1);19}20}2122Console.WriteLine("实验结束！");23Console.ReadKey();24}2526///
2.优化
暴力解法可以得到结果，但这肯定是不能让人满意的。现在回过头来再分析这个题。
第一次操作，每个灯的开关都被按一次；
第二次操作，2的倍数的开关都被按一次；
.....
下面列出前十次，前十个数的具体情况
可以看到，最下面一列是操作的次数，操作次数为奇数次的，灯最后是打开的状态，是偶数次，则为关闭。
被操作的规律如下:
灯1:1
灯2:1，2
灯3:1，3
灯4:1，2，4
...
依次写下去，就可以发现，每个灯被操作的步骤，其实为此灯编号的因数。
如灯36被操作的步骤:1，2，3，4，6，9，12，18，36
此时题目转化为求[1-100]100个数中，因数个数为奇数的数的数量是多少。
因为最近在学习Python，求因数的算法用python语言给出，3.4版本运行成功如下：
1defgetZYS(n):2x=23zys=[]4zys.extend([1,n])5whilex*x<=n:6ifn%x==0:7ifx*x==n:8zys.extend([x])9else:10zys.extend([x,n//x])11x+=112returnzys1314n=input('请输入一个正整数:')15n=int(n)16lb=getZYS(n)17lb=sorted(lb)18print(lb)19此时，题目的解法已经第一次被推广，在一定程度上，我们已经可以解决更多类似的问题。推广后的解法请自行试着去解决。
3.就事论事
求一个正整数的质数的过程，如上面代码所示，其实就是对某个数平方根以下的数试着求余，但具体到本题而言，转化一下描述为，怎样快速判断一个数的因数个数是否为奇数。
请看上面的代码，第7-10行，如果能深刻理解这几行，上面所述的题目会有更快的解法。
我们注意到，求一个数因数的过程，是从1开始到其平方根，除平方根外，其他的因数都是成对的出现！，也就是，只有平方数的因数是奇数个！，100以内的平方数只有10个，分别是1，4，9，16，25，36，49，64，81，100，所以上述题目的最后结果是10个灯最后是亮着的。
优化完的代码，注释要多一些，代码本身将非常之少，因为100的平方根是10，所以最后亮10盏灯。
你明白了没有？
附：
求1<=i<=10**12范围内所有d(i)的和的末12位，d(i)表示i的正约数的和，i为整数