Question

Write python code to display the prime factors of any user given number

Answer 1

I would start with the highest prime that is close to half of the number and work down. Also, you might want to check if it is prime right off.

Answer 2

These were from a couple of years back, but should still work.


def makeprimelist(bound):
max_ndx = (bound - 1) / 2
sieve = [True] * (max_ndx + 1)
for ndx in range(int(bound ** 0.5) / 2):
if sieve[ndx]:
num = ndx * 2 + 3
sieve[ndx+num:max_ndx:num] = [False] * ((max_ndx-ndx-num-1)//num + 1)
return [2] + [ndx * 2 + 3 for ndx in range(max_ndx) if sieve[ndx]]

def factors(x,unique=0):
if x ==1:return [1]
pl = makeprimelist(x)
tmp = x
factors=[]
while tmp > 1:
for p in pl:
if tmp%p==0:
factors.append(p)
tmp=tmp/p
if unique:
factors.sort()
i=0
while i < len(factors)-1:
if i < len(factors) and factors[i]==factors[i+1]:
factors.remove(factors[i])
factors[i]=factors[i]*factors[i]
else:
i+=1

return factors

Answer 3

and i make no claims that that is the best way to implement either of the functions just the ones i used when i was learning python and playing on projecteuler.net