Returns all the prime factors of a positive integer
# -*- coding: utf-8 -*-
import math
#def is_square(apositiveint):
# x = apositiveint // 2
# seen = set([x])
# while x * x != apositiveint:
# x = (x + (apositiveint // x)) // 2
# if x in seen: return False
# seen.add(x)
# return True
#
#for i in range(110, 130):
# print i, is_square(i)
#FermatFactor(N): // N should be odd
# a ← ceil(sqrt(N))
# b2 ← a*a - N
# while b2 isn't a square:
# a ← a + 1 // equivalently: b2 ← b2 + 2*a + 1
# b2 ← a*a - N // a ← a + 1
# endwhile
# return a - sqrt(b2) // or a + sqrt(b2)
def prime_factors(n):
"Returns all the prime factors of a positive integer"
factors = []
d = 2
while (n > 1):
while (n%d==0):
factors.append(d)
n /= d
d = d + 1
if (d*d>n):
if (n>1): factors.append(n);
break;
return factors