小b有n个关闭的灯泡，编号为1...n。
小b会进行n轮操作，第i轮她会将编号为i的倍数的灯泡的开关状态取反，即开变成关，关变成开。
求n轮操作后，有多少灯泡是亮着的。
输入一个数字表示灯泡数n，其中1＜n≤10000000
输出一个数字表示最终亮着的灯泡数
3
1
打表发现规律：第i^2的灯是亮的，扫描一遍符合的i；复杂度logn
#include<Iostream> using namespace std; bool a[1000]; int main(){ int n; cin>>n; int sum=0; for(int i=1;;i++){ if(i*i>n) break; sum++; } cout<<sum<<endl; return 0; }
原文：https://www.cnblogs.com/yfr2zaz/p/10739956.html