Stub : 63 --> '(3**2)(7)' You get the idea. The return needs to be '(p1**n1)(p2**n2)..(pk**nk)'
How? I admit my first shot was crappy - maintain a dictionary of powers. Then I saw the "best" solution :
def primeFactors(n):
ret = ''
for i in xrange(2, n + 1):
num = 0
while(n % i == 0):
num += 1
n /= i
if num > 0:
ret += '({}{})'.format(i, '**%d' % num if num > 1 else '')
if n == 1:
return ret
Hokay, what's going on here? Really cute way of building up the string as you go along. But, he looking at all the numbers from 2 to n. Do you need to? The even numbers? :) Once you've extracted 2, you'll never need to consider an even number again. Then, to what extend to you need to go? Do you need to go past sqrt(n)? Take 21. You get 3 out of it and stop at 5 because that's close to sqrt(21). What are you left with after you extract 3? That's right! 7. So, just stop at sqrt(n) and look at what you have and if you have something greater than 1, that's the largest prime factor.
So :
def prime_factors(n):
ret = ''
for i in [2] + list(range(3, int(n**0.5+1),2)) :
pow = 0
while n % i == 0 :
pow += 1
n = n // i
if pow > 0 : ret += '({}{})'.format( i, '**%d' % pow if pow > 1 else '' )
if n == 1 : return ret
return ret + '({})'.format( n ) if n > 1 else ''
Plagiarism? Yes. Something useful added? Probably :)
Comments
Post a Comment