小明特别喜欢开关灯。
现在有编号为1～100的灯初始状态是全开着的，现进行如下操作：
- 编号是1的倍数的灯拨一下开关；
- 编号是2的倍数的灯再拨一下开关；
- 编号是3的倍数的灯再拨一下开关；
- …………
- 如此直到100的倍数。
问：此时还有多少盏灯仍然是开着的。
这个问题很简单，它其实就是在问：1~100中，有多少约数个数为偶数的数字。（偶数次操作的效果是没变化）
然后把这个分析翻译成C程序代码：
#include<stdio.h>
#define NUM 100
int main(){
int n=0;
for(int i=1;i<=NUM;i++){
int p=0;
for(int j=1;j<=i;j++)
if(i%j==0) p++;
if(p%2==0) n++;
}
printf("%d\n",n);
return 0;
}
这样很快地就可以得到结果90，之后就结束了吗？
不，这个解法是比较傻的，比较慢的——试着换个加强版的问题：
87654321盏灯!
小明现在有87654321盏灯⊙﹏⊙b汗。
现在有编号为1～87654321的灯初始状态是全开着的，现进行如下操作：
- 编号是1的倍数的灯拨一下开关；
- 编号是2的倍数的灯再拨一下开关；
- 编号是3的倍数的灯再拨一下开关；
- …………
- 如此直到87654321的倍数。
问：此时还有多少盏灯仍然是开着的。
还按刚才的解法来？（对代码稍作修改）
#include<stdio.h>
#define NUM 87654321//改个数
int main(){
int n=0;
for(int i=1;i<=NUM;i++){
int p=0;
for(int j=1;j<=i;j++)
if(i%j==0) p++;
if(p%2==0) n++;
}
printf("%d\n",n);
return 0;
}
运行起来时间似乎有点长啊。（我不想等下去了）那要怎么办？
回到问题上来：约数个数为偶数的数字有什么特点，或者说，约数个数为奇数的数字有什么特点？
从1，2，3，4，5，6，7，8，9，10，……下手，会发现：约数个数为奇数的数字是1，4，9，……这些完全平方数。
所以大幅更新一下代码：
#include<stdio.h>
#include<math.h>
#define NUM 87654321
int main(){
int n=NUM;
for(long i=1;i<=NUM;i++){
int r=(int)sqrt(i);
if(r*r==i) n--;
}
printf("%d\n",n);
return 0;
}
这样就能在一个较为合理的时间内得到答案87644959了，不过还是不够快。
于是再想一下，得到的终极代码是：
#include<stdio.h>
#include<math.h>
#define NUM 87654321
int main(){
int n=NUM;
printf("%d\n",n-(int)sqrt(n));
return 0;
}
这样甚至可以用纸笔解得答案。
所以说，虽然编程这项技能的确可以帮助我们思考问题、解决问题，但归根结底，思维才是最关键的。（别因为有了电脑，废了人脑）
