##
Problem 3 - Largest prime factor

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

####
its time complexity is O(n) (linear) with the largest factor

It means it's fast for 600851475143 but not for 600851475145

def get_prime_factors(number):
factor=2
while number <> 1 & factor <= number:
factor += 1
while number % factor == 0:
yield factor
number /= factor
for x in get_prime_factors(600851475143):
print x

####
its time complexity is O(sqrt(n)) (fractional power) with the largest factor.

def get_prime_factors(number):
while number % 2 == 0:
yield 2
number /= 2
factor=1
maxFactor = int(number ** .5)
while number <> 1 & factor <= maxFactor:
factor += 2
while number % factor == 0:
yield factor
number /= factor
if number > 1:
yield number
for x in get_prime_factors(600851475145):
print x

## No comments:

Post a Comment