废话少说，开刷（一定要看到最后，文末有惊喜）
今天随机一题随到一个比较好玩的题，以前经常听说这种题目，但都不是编程序解决的，所以看到这个题还是非常感兴趣的。
题目：
初始时有?n 个灯泡处于关闭状态。第一轮，你将会打开所有灯泡。接下来的第二轮，你将会每两个灯泡关闭第二个。
第三轮，你每三个灯泡就切换第三个灯泡的开关（即，打开变关闭，关闭变打开）。第 i 轮，你每 i 个灯泡就切换第 i 个灯泡的开关。直到第 n 轮，你只需要切换最后一个灯泡的开关。
找出并返回 n?轮后有多少个亮着的灯泡。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/bulb-switcher
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。几个testcases：
0 --> 0
1 --> 1
2 --> 1
3 --> 1
100 --> 31
动手刷吧，这个不简单吗，弄个数组，第一轮，1个一个走一遍；第二轮2个2个走一遍；第三轮，3个3个走一遍。。。。。
5分钟，代码就出来了
public int BulbSwitch(int n)
{
bool[] num = new bool[n];
for (var i = 0; i < n; i++)
{
num[i] = true;
}
// 先来一个最基本的算法，挨个循环
for (var i=2; i<=n; i++)
{
for(var j=i-1; j<n; j+=i)
{
num[j] = !num[j];
}
}
var cnt = 0;
for (var i = 0; i < n; i++)
{
if(num[i] == true)
{
cnt++;
}
}
return cnt;
}
?做了几个UT，上面几个case跑出来了，完美。
最后看到题目上一行小字，0<=n<=10e9，最大是10亿，测一下，发现跑不出来了 [哭]
于是回头看一下，跑了一个1万，10万，100万，到1000万，发现到1亿，UT要16秒才能出来。完犊子了。
?别想了，作为一个中等难度的题，不是这么简单的，换算法吧。
于是想到了另一个算法：
第一个灯，只有1的倍数，操作1次，亮；
第二个灯，有1和2的倍数，操作2次，灭；
第三个灯，有1和3的倍数，操作2次，灭；
第四个灯，有1、2、4的倍数，操作3次，亮；总结：每个数字获取除了1和他自己的因数，奇亮偶灭。
想到以上想法后，再仔细一项，貌似还是行不通啊。这个针对单个数的测试会快很多，但针对所有数字的计算，还是很大的计算量。?
于是就想到了传说中的最不要脸的查表法，给部分关键数字的数据保存下来，然后按照这个关键数字往上查，关键数字以下的就直接加一个数字就完事了。
太晚了，另外除了这个以外，还想再想想有没有其他的思路。
另外发现一个奇怪的现象：
1 - 1
10 - 3
100 - 10
1,000 - 31
10,000 - 100
100,000 - 316
1,000,000 - 1000
10,000,000 - 3162
100,000,000 - 10000
1,000,000,000 - 31622
睡觉，梦里跟周公讨论讨论去。?
-----
今天继续，昨天想到，要用查表法，然后略微思考了一下，第一反应是常规的指数方式，比如，或者
，但仔细一想，发现并不合适，因为不能递归指数级查找，所以从1亿到10亿之间，9亿的数量要查询，1-10就9个数字要查询，差1亿倍的数量级，显然不合适。那就需要平均分了。
那平均分的话，就看良心了。我可以每1亿一个区间分10个区间，也可以每10000分10万个区间。反正这个数字都可以写个程序跑出来然后写到固定的数组里。程序又没有限制我程序文本的大小。显然这样不要脸的行为属于最后的方法，哈哈。
另外就上面那个奇怪的现象，我想先在这个现象上走深入一点看看。
我算了1000万到1亿的数字，画了一个图，寄希望于根据提醒反推出公式，有公式，那就超级简单了。
更细节一点的，10000以内的，锯齿感严重
初步一看，有点像log(n)的公式，这个。，。自己数学不好，网搜去。
搜了一半，说有一个高阶逼近法，然后就兴趣盎然了，为了一个算法去学一个高阶数学公式。。。
回头尝试了2件事：
- 第一，从1到10000，给数字打印了下来，就是上面那个图的数据源；
- 第二，从1到10000，打印了有数字变化的数字，就下面这个图
结果发现有大惊喜，这每一个数，不正好是！！！
程序员一句我屮艸芔茻，马上换个算法：
return (int)Math.Sqrt(n);跑路，验证，通过！
总结：
有啥好总结的，一贯的说法，算法的终极目标，是把算法推算成公式，公式永远比循环啥的快！