#NEWLINE# def _factorint_small( factors , n , limit , fail_max ) : #NEWLINE# #INDENT# '\n    Return the value of n and either a 0 (indicating that factorization up\n    to the limit was complete) or else the next near-prime that would have\n    been tested.\n\n    Factoring stops if there are fail_max unsuccessful tests in a row.\n\n    If factors of n were found they will be in the factors dictionary as\n    {factor: multiplicity} and the returned value of n will have had those\n    factors removed. The factors dictionary is modified in-place.\n\n    ' #NEWLINE# def done( n , d ) : #NEWLINE# #INDENT# "return n, d if the sqrt(n) wasn't reached yet, else\n           n, 0 indicating that factoring is done.\n        " #NEWLINE# if ( ( d * d ) <= n ) : #NEWLINE# #INDENT# return ( n , d ) #NEWLINE# #UNINDENT# return ( n , 0 ) #NEWLINE# #UNINDENT# d = 2 #NEWLINE# m = trailing ( n ) #NEWLINE# if m : #NEWLINE# #INDENT# factors [ d ] = m #NEWLINE# n >>= m #NEWLINE# #UNINDENT# d = 3 #NEWLINE# if ( limit < d ) : #NEWLINE# #INDENT# if ( n > 1 ) : #NEWLINE# #INDENT# factors [ n ] = 1 #NEWLINE# #UNINDENT# return done ( n , d ) #NEWLINE# #UNINDENT# m = 0 #NEWLINE# while ( ( n % d ) == 0 ) : #NEWLINE# #INDENT# n //= d #NEWLINE# m += 1 #NEWLINE# if ( m == 20 ) : #NEWLINE# #INDENT# mm = multiplicity ( d , n ) #NEWLINE# m += mm #NEWLINE# n //= ( d ** mm ) #NEWLINE# break #NEWLINE# #UNINDENT# #UNINDENT# if m : #NEWLINE# #INDENT# factors [ d ] = m #NEWLINE# #UNINDENT# if ( ( limit * limit ) > n ) : #NEWLINE# #INDENT# maxx = 0 #NEWLINE# #UNINDENT# else : #NEWLINE# #INDENT# maxx = ( limit * limit ) #NEWLINE# #UNINDENT# dd = ( maxx or n ) #NEWLINE# d = 5 #NEWLINE# fails = 0 #NEWLINE# while ( fails < fail_max ) : #NEWLINE# #INDENT# if ( ( d * d ) > dd ) : #NEWLINE# #INDENT# break #NEWLINE# #UNINDENT# m = 0 #NEWLINE# while ( ( n % d ) == 0 ) : #NEWLINE# #INDENT# n //= d #NEWLINE# m += 1 #NEWLINE# if ( m == 20 ) : #NEWLINE# #INDENT# mm = multiplicity ( d , n ) #NEWLINE# m += mm #NEWLINE# n //= ( d ** mm ) #NEWLINE# break #NEWLINE# #UNINDENT# #UNINDENT# if m : #NEWLINE# #INDENT# factors [ d ] = m #NEWLINE# dd = ( maxx or n ) #NEWLINE# fails = 0 #NEWLINE# #UNINDENT# else : #NEWLINE# #INDENT# fails += 1 #NEWLINE# #UNINDENT# d += 2 #NEWLINE# if ( ( d * d ) > dd ) : #NEWLINE# #INDENT# break #NEWLINE# #UNINDENT# m = 0 #NEWLINE# while ( ( n % d ) == 0 ) : #NEWLINE# #INDENT# n //= d #NEWLINE# m += 1 #NEWLINE# if ( m == 20 ) : #NEWLINE# #INDENT# mm = multiplicity ( d , n ) #NEWLINE# m += mm #NEWLINE# n //= ( d ** mm ) #NEWLINE# break #NEWLINE# #UNINDENT# #UNINDENT# if m : #NEWLINE# #INDENT# factors [ d ] = m #NEWLINE# dd = ( maxx or n ) #NEWLINE# fails = 0 #NEWLINE# #UNINDENT# else : #NEWLINE# #INDENT# fails += 1 #NEWLINE# #UNINDENT# d += 4 #NEWLINE# #UNINDENT# return done ( n , d )