【Project Eular - Python】Problem 3: Largest prime factor

题目给出了一个12位数的数字，然后要求得到其最大的质因数。至于质因数是什么，这个是数学的范畴，这里也就不去赘述了。

【一】原始脚本

最早的想法就是从2开始，一直到目标数，对出现的每个数字先做判断其是否为目标是的质因数，如果是，放到一个数组里，最后取数组中的最大值即可，代码如下：

执行脚本的时候才发现，计算量实在是太大了，一个小时才计算了9位数级别，照这样下去，目测整整运行3，4天都一定能得到结果，这个离我们要求的12位数级差太多了，因此有了下面的第二版优化。

【二】初级优化

由于取的值只最大值，所以就想到了从目标数开始，往下递减，代码如下：

执行脚本，虽然比上面有所提高，但仍然满足不了我们的要求，因此想到了下面的方法，也就是终极版的优化.

【三】最后的优化版

后来考虑到这个每个数都能通过质因数相乘得到，因此在实际运算中，我们把目标数除以较小的质因数，这样目标数就会进一步被分解，这样的话，我们就能避免很多不必要的运算量了。举例来说，我们要计算1000的最大质因数，第一步我们会发现2是其中的一个，那么目标数就从1000变成了500，这样相对于上面的两种算法，我们至少节省了一半的时间了；然后递归计算，直到我们得到最大的质因数。算法如下：

在windows eclipse和Ubuntu环境下，实测，得到目标数600851475143的最大质因数为6857；而最神奇的是，得到这个数仅仅需要不到1秒钟。

至此，问题三成功解决，上传答案，正确。