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
分享到:
相关推荐
Everybody knows any number can be combined by the prime number. Now, your task is telling me what position of the largest prime factor. The position of prime 2 is 1, prime 3 is 2, and prime 5 is 3, ...
将您的过程解决方案编码到lib/largest_prime_factor.rb文件中。 将您的面向对象的解决方案编码到lib/oo_largest_prime_factor.rb文件中。 确保将最大质数因子设置为等于LargestPrimeFactor类的number属性。 运行...
指示将您的过程解决方案编码到lib/largest_prime_factor.rb文件中。 将您的面向对象的解决方案编码到lib/oo_largest_prime_factor.rb文件中。 确保将最大质数因子设置为等于LargestPrimeFactor类的number属性。 运行...
将您的过程解决方案编码到lib/largest_prime_factor.rb文件中。 将您的面向对象的解决方案编码到lib/oo_largest_prime_factor.rb文件中。 确保将最大质数因子设置为等于LargestPrimeFactor类的number属性。 运行...
将您的过程解决方案编码到lib/largest_prime_factor.rb文件中。 将您的面向对象的解决方案编码到lib/oo_largest_prime_factor.rb文件中。 确保将最大质数因子设置为等于LargestPrimeFactor类的number属性。 运行...
将您的过程解决方案编码到lib/largest_prime_factor.rb文件中。 将您的面向对象的解决方案编码到lib/oo_largest_prime_factor.rb文件中。 确保将最大质数因子设置为等于LargestPrimeFactor类的number属性。 运行...
将您的过程解决方案编码到lib/largest_prime_factor.rb文件中。 将您的面向对象的解决方案编码到lib/oo_largest_prime_factor.rb文件中。 确保将最大质数因子设置为等于LargestPrimeFactor类的number属性。 运行...
将您的过程解决方案编码到lib/largest_prime_factor.rb文件中。 将您的面向对象的解决方案编码到lib/oo_largest_prime_factor.rb文件中。 确保将最大质数因子设置为等于LargestPrimeFactor类的number属性。 运行...
将您的过程解决方案编码到lib/largest_prime_factor.rb文件中。 将您的面向对象的解决方案编码到lib/oo_largest_prime_factor.rb文件中。 确保将最大质数因子设置为等于LargestPrimeFactor类的number属性。 运行...
将您的过程解决方案编码到lib/largest_prime_factor.rb文件中。 将您的面向对象的解决方案编码到lib/oo_largest_prime_factor.rb文件中。 确保将最大质数因子设置为等于LargestPrimeFactor类的number属性。 运行...
将您的过程解决方案编码到lib/largest_prime_factor.rb文件中。 将您的面向对象的解决方案编码到lib/oo_largest_prime_factor.rb文件中。 确保将最大质数因子设置为等于LargestPrimeFactor类的number属性。 运行...
将您的过程解决方案编码到lib/largest_prime_factor.rb文件中。 将您的面向对象的解决方案编码到lib/oo_largest_prime_factor.rb文件中。 确保将最大质数因子设置为等于LargestPrimeFactor类的number属性。 运行...
将您的过程解决方案编码到lib/largest_prime_factor.rb文件中。 将您的面向对象的解决方案编码到lib/oo_largest_prime_factor.rb文件中。 确保将最大质数因子设置为等于LargestPrimeFactor类的number属性。 运行...
将您的过程解决方案编码到lib/largest_prime_factor.rb文件中。 将您的面向对象的解决方案编码到lib/oo_largest_prime_factor.rb文件中。 确保将最大质数因子设置为等于LargestPrimeFactor类的number属性。 运行...
将您的过程解决方案编码到lib/largest_prime_factor.rb文件中。 将您的面向对象的解决方案编码到lib/oo_largest_prime_factor.rb文件中。 确保将最大质数因子设置为等于LargestPrimeFactor类的number属性。 运行...
将您的过程解决方案编码到lib/largest_prime_factor.rb文件中。 将您的面向对象的解决方案编码到lib/oo_largest_prime_factor.rb文件中。 确保将最大质数因子设置为等于LargestPrimeFactor类的number属性。 运行...
将您的过程解决方案编码到lib/largest_prime_factor.rb文件中。 将您的面向对象的解决方案编码到lib/oo_largest_prime_factor.rb文件中。 确保将最大质数因子设置为等于LargestPrimeFactor类的number属性。 运行...
将您的过程解决方案编码到lib/largest_prime_factor.rb文件中。 将您的面向对象的解决方案编码到lib/oo_largest_prime_factor.rb文件中。 确保将最大质数因子设置为等于LargestPrimeFactor类的number属性。 运行...
将您的过程解决方案编码到lib/largest_prime_factor.rb文件中。 将您的面向对象的解决方案编码到lib/oo_largest_prime_factor.rb文件中。 确保将最大质数因子设置为等于LargestPrimeFactor类的number属性。 运行...
将您的过程解决方案编码到lib/largest_prime_factor.rb文件中。 将您的面向对象的解决方案编码到lib/oo_largest_prime_factor.rb文件中。 确保将最大质数因子设置为等于LargestPrimeFactor类的number属性。 运行...