找出特定数字的最大质因数

首先我们来看个例子：
13195的质因数为 5， 7， 13， 29， 其中29就是最大的质因数。
现在让我们来计算600851475143的最大质因素。

当看到这个问题的时候，我们首先要判断哪些是质数，而这些质数中又有哪些是可以被600851475143整除的。因此需我们要有个数：index 不断增长，并且找出index中的质数，然后计算index是否可以被num整除，如果可以的话，重设num为被整除后的值。 很明显这操作是个循环，有一点可以肯定，就是在index的增长过程中，永远不可能大于num，因此我们的循环也有了范围判断了
下面我们来写代码：

from math import sqrt

# 质数判断
def isPrime(n):
    for i in range(2, int(sqrt(n))+1):
        if n % i == 0:
            return False
    return True

index = 2
num = 600851475143
maxPrime = None

while index <= num:
    if isPrime(index) and num % index == 0:
        num /= index
        maxPrime = index
    index += 1

print maxPrime

评论

2 楼 mxzodiac 2011-09-02  

其实可以倒序求平方根，对最大整除数递减相除，直到最后一个就是最大质数了。
原来你很早就看Project eulur了～
小Z路过～

1 楼 chyanog 2010-05-04  

这个方法有点儿繁琐了，素性判断没有必要的