【从实例开始学python】3.求最大质因子

README：

本教程主要讲python3，python2的小伙伴可以自行根据需求转换；

推荐在linux平台下操作，如果没有可以安装虚拟机，具体教程可以百度/谷歌；

推荐使用发行包anaconda3，具体安装方法可以百度；

我代码的测试环境的python版本是3.6.4。

我所选的题目大部分都来自于https://projecteuler.net/，大家可以自行查看参阅。

问题三：

问题分析1：

一个数的最大质因子，需要满足三个条件，一是其必须是质数，二是他需要是该数的因子，三是其是最大的。

以此来分析，最简单的寻找最大质因子的方法就是从该数本身开始向下遍历，找到第一是质数的因子。

代码1：(project3_01.py)

from math import sqrt

def is_prime(n):

if n == 1:

return False

if n == 2:

return True

if n % 2 == 0:

return False

for i in range(3, int(sqrt(n)//1)+1, 2):

if n % i == 0:

return False

return True

if __name__ == "__main__":

for i in range(n, 1, -1):

if n % i == 0 and is_prime(n):

break

print("Max prime factor of %d is %d." % (n, i))

sqrt表示求正平方根的函数，这里在判断一个数是否是质数时使用了两个小技巧还节省时间：

任何一个合数至少有一个不超过其平方根的因子；

任何一个非偶数的合数至少有一个不小于3的奇数因子。

虽然已经使用了以上两个技巧来帮助减少时间，但是整个程序仍然花费了不少时间，10分钟仍然没有跑出来结果。

问题分析2：

我们必须想出更好的解决方案出来帮助我们解决问题。

一个显而易见的方案就是减少遍历次数，因为A的因子的因子必然也是A的因子，这样，我们如果对A进行质因子分解的话，最后得到的哪个质数必然时A的最大质因子。

代码2：(project3_02.py)

代码2包含了一个因子分解的函数，factorize

factorize接收一个正的大于等于2的自然数n，返回其最的质因子和最小质因子的商。其中调用divmod函数带余除法，返回商和余数。

代码的速度非常快，只有0.02秒就可以得到正确结果6857。

代码的输出是这样的：

Max prime factor of 600851475143 is 6857.

问题分析3：

我们在代码2中隐含了一个逻辑，也就是在循环调用factorize的时候，其分解得到的因子是单调递增的，基于这个逻辑，我们其实可以进一步改造我们的程序。

代码3：(project3_03.py)

from math import sqrt

def factorize(n, start=2):

for i in range(start, int(sqrt(n)//1)+1):

q, r = divmod(n, i)

if r == 0:

return i, q

return n, 1

def max_prime_factor(n):

f1 = 2

while n > 1:

f1, n = factorize(n, f1)

return f1

if __name__ == "__main__":

f = max_prime_factor(n)

print("Max prime factor of %d is %d." % (n, f))

代码3输出的结果和代码2是一样的，消耗的时间也接近。

练习3：

回文数是指正着读和反着读都一样的数，而由两位数的乘积构成的最大回文数是9009 = 91 × 99。

找到最大的且是两个3位数的乘积的回文数。