Pages

Project Euler Problem #3 with Python: Greatest Prime Factor

This is not very efficient, but here is my solution to Project Euler Problem 3 using python.

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