A O ( log n ) function returning prime factorization by dividing by smallest prime factor at every step
def getFactorization ( x ) : NEW_LINE INDENT ret = list ( ) NEW_LINE while ( x != 1 ) : NEW_LINE INDENT ret . append ( spf [ x ] ) NEW_LINE x = x // spf [ x ] NEW_LINE DEDENT return ret NEW_LINE DEDENT