A O ( log n ) function returning primefactorization 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 temp = spf [ x ] NEW_LINE ret . append ( temp ) NEW_LINE while ( x % temp == 0 ) : NEW_LINE INDENT x = x // temp NEW_LINE DEDENT DEDENT return ret NEW_LINE DEDENT