from math import ceil
class Prime(object):
primes = set([2])
def is_prime(self,n):
n = float(n)
if n < 2:
return False
else:
for i in xrange(2,int(ceil(n**.5))):
f = n/i
if not f%1:
return False
else:
return True
def greatest_prime_factor(self,n):
n = float(n)
if self.is_prime(n): return n
prime_factors = set()
for i in xrange(2,int(ceil(n**.5))):
f = n/i
if not f%1:
if self.is_prime(f):
prime_factors.add(f)
if self.is_prime(i):
prime_factors.add(i)
return max(prime_factors)
prime = Prime()
n = 600851475143
prime.greatest_prime_factor(n)Edit:After looking at some of the other answers, I made the following as translated from a fantastic c answer:
def greatest_prime_factor(n):
divisor = 2
while n > 1:
print divisor
if not n%divisor:
n /= divisor
divisor -= 1
divisor += 1
return divisor
0 comments:
Post a Comment