tomislav-b
2/2/2015 - 6:28 PM

Returns all the prime factors of a positive integer

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