小明特別喜歡開關(guān)燈。
現(xiàn)在有編號(hào)為1～100的燈初始狀態(tài)是全開著的，現(xiàn)進(jìn)行如下操作：
- 編號(hào)是1的倍數(shù)的燈撥一下開關(guān)；
- 編號(hào)是2的倍數(shù)的燈再撥一下開關(guān)；
- 編號(hào)是3的倍數(shù)的燈再撥一下開關(guān)；
- …………
- 如此直到100的倍數(shù)。
問：此時(shí)還有多少盞燈仍然是開著的。
這個(gè)問題很簡單，它其實(shí)就是在問：1~100中，有多少約數(shù)個(gè)數(shù)為偶數(shù)的數(shù)字。（偶數(shù)次操作的效果是沒變化）
然后把這個(gè)分析翻譯成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;
}
這樣很快地就可以得到結(jié)果90，之后就結(jié)束了嗎？
不，這個(gè)解法是比較傻的，比較慢的——試著換個(gè)加強(qiáng)版的問題：
87654321盞燈!
小明現(xiàn)在有87654321盞燈⊙﹏⊙b汗。
現(xiàn)在有編號(hào)為1～87654321的燈初始狀態(tài)是全開著的，現(xiàn)進(jìn)行如下操作：
- 編號(hào)是1的倍數(shù)的燈撥一下開關(guān)；
- 編號(hào)是2的倍數(shù)的燈再撥一下開關(guān)；
- 編號(hào)是3的倍數(shù)的燈再撥一下開關(guān)；
- …………
- 如此直到87654321的倍數(shù)。
問：此時(shí)還有多少盞燈仍然是開著的。
還按剛才的解法來？（對(duì)代碼稍作修改）
#include<stdio.h>
#define NUM 87654321//改個(gè)數(shù)
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;
}
運(yùn)行起來時(shí)間似乎有點(diǎn)長啊。（我不想等下去了）那要怎么辦？
回到問題上來：約數(shù)個(gè)數(shù)為偶數(shù)的數(shù)字有什么特點(diǎn)，或者說，約數(shù)個(gè)數(shù)為奇數(shù)的數(shù)字有什么特點(diǎn)？
從1，2，3，4，5，6，7，8，9，10，……下手，會(huì)發(fā)現(xiàn)：約數(shù)個(gè)數(shù)為奇數(shù)的數(shù)字是1，4，9，……這些完全平方數(shù)。
所以大幅更新一下代碼：
#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;
}
這樣就能在一個(gè)較為合理的時(shí)間內(nèi)得到答案87644959了，不過還是不夠快。
于是再想一下，得到的終極代碼是：
#include<stdio.h>
#include<math.h>
#define NUM 87654321
int main(){
int n=NUM;
printf("%d\n",n-(int)sqrt(n));
return 0;
}
這樣甚至可以用紙筆解得答案。
所以說，雖然編程這項(xiàng)技能的確可以幫助我們思考問題、解決問題，但歸根結(jié)底，思維才是最關(guān)鍵的。（別因?yàn)橛辛穗娔X，廢了人腦）
