“喜欢开关灯的小明”问题

问题来源

小明特别喜欢开关灯。

现在有编号为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;
}

这样甚至可以用纸笔解得答案。

所以说，虽然编程这项技能的确可以帮助我们思考问题、解决问题，但归根结底，思维才是最关键的。（别因为有了电脑，废了人脑）