优化的重要性

先看一个简单的引例
输入一个数n,输出1至n中所有的质数。
如果n<=100,我们可以考虑打表（手动滑稽）.
如果n<=1000,考虑到计算机的运行速度，我们可以无脑根据质数的定义暴力从1到n依次判断。
当然我们可以发现，其实如果在根号下n之前就存在n的因子，那显然不需要判断根号n之后的值。我们对其简单修改。
当然我们还可以通过一些奇技淫巧再减少一点点循环次数。

再想优化，便要运用一些数学知识，比如说去掉判断偶数的情况？甚至扩展到所有非素数的倍数的情况，同时根据数学知识，大于6的素数，一定为6k+1或6k+5的形式，这又减少了循环次数。我们还可以在出现因子后立刻跳出循环。
通过这个简单的引例，我们意识到，写出程序并不是结束，要尝试对其进行优化。毕竟谁也不想看到一个时间复杂度为阶乘级的算法。算法优化，百度百科上的定义为：算法优化是指对算法的有关性能进行优化，如时间复杂度、空间复杂度、正确性、健壮性。由于算法应用情景变化很大，算法优化可以使算法具有更好泛化能力。
在常见的算法中，搜索算法较为全能，但是他的复杂度也是非常之高。我们可以具体问题具体分析，根据需要灵活的使用各种优化方法，比如剪枝优化，去降低时间复杂度。再给出一个经典例子。

显然这道题可以用深度优先搜索解决。当然直接爆搜复杂度也是十分感人。在这里我给出一个大致思路。程序就不放上了