No.3 The largest prime factor of number

Q: The prime factors of 13195 are 5, 7, 13 and 29.
   What is the largest prime factor of the number 600851475143 ?

################################
# shell                        #
# echo 600851475143 | factor   #
#600851475143: 71 839 1471 6857#
################################

import math

''' method one
    一个数n的最大公约数一定小于这个数的开方s
    先判断2是否是这个数的约数
    从3到s，查找可以被n整除而且不是2的倍数的数，div
    根据div找到s到n之间的可以被n整除而不是2的倍数的数，divTemp
    从div+divTemp中筛选，用最大的数依次除以小的数，看是否有约数，没有的话，就是要找的数
'''
n = 600851475143
div = []
if n % 2 == 0: div.append(2)
div += [x for x in range(3, int(math.sqrt(n))) if (n % x == 0 and x % 2 != 0)]
divTemp = [n/x for x in div if n/x%2 != 0]
div += divTemp
i, j = 0, len(div) - 1
while j > i:
   if div[j] % div[i] == 0: i,j = 0,j-1
   else: i += 1
print div[j]

'''
#method two
def primeNum(n):
    pm = n - 1
    while pm > 1:
        if n % pm:
            pm = pm - 1
            continue
        else:
            return 0
    return n

n = 600851475143
n2 = int(math.sqrt(n))
#n = 13195
i = n2 - 1
while i > 2:
    if not n % i:
        print "even-valued=%d" %i
        if primeNum(i):
            print "prime=%d" %i
            exit()
    i = i-1
'''           
'''
    so fast
    奇特的方法，把number分成多个数相乘的积，从2开始，如果可以整除，就一直除下去，直到再也不能被2整除,如此，得到的数都是素数
    例如，100， 得到的值是[2,2,5,5]
'''

#roots = []; product = 1; x = 2; number = input("number?: "); y = number
roots = []; product = 1; x = 2; number = 600851475143; y = number
while product != number:
while (y % x == 0):
roots.append(x)
y /= x
product *= roots[-1]
x += 1
print roots

'''method 4,没有考虑2的情况，看数字得到2不可能'''
d, n = 3, 600851475143
while (d * d < n):
    if n % d == 0: n /= d
    else: d += 2
print n