`
诗意的栖居
  • 浏览: 273792 次
  • 性别: Icon_minigender_2
  • 来自: 北京
社区版块
存档分类
最新评论

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
分享到:
评论

相关推荐

Global site tag (gtag.js) - Google Analytics