def prime_factors(n):
#Step 1. Create an empty list of factors
factors = []
#Step 2. While n is even, add 2 to list of factors and proceed to divide n by 2 until
#it is no longer a factor of 2
while n % 2 == 0:
n = n / 2
#only add if not already in list of factors
if 2 not in factors:
factors.append(2)
#Step 3. Set f to 3
f = 3
#Step 4. Calculate quotient q and remainder f
q = 0
r = 0
while True:
q = int(n / f)
r = n % f
#Step 5. If r > 0, f = f+2 and try again
if r > 0:
f += 2
else:
#Step 6. Otherwise, add f to list of factors and set n = q
factors.append(f)
n = q
#Step 7. If n < f^2 then add n to the list of factors and stop
if n < f ** 2:
factors.append(n)
break
#Step 8. Continue with the loop
#Loop terminated, return the factors
return factors