#NEWLINE# def multiplicity( p , n ) : #NEWLINE# #INDENT# '\n    Find the greatest integer m such that p**m divides n.\n\n    Examples\n    ========\n\n    >>> from sympy.ntheory import multiplicity\n    >>> from sympy.core.numbers import Rational as R\n    >>> [multiplicity(5, n) for n in [8, 5, 25, 125, 250]]\n    [0, 1, 2, 3, 3]\n    >>> multiplicity(3, R(1, 9))\n    -2\n\n    ' #NEWLINE# try : #NEWLINE# #INDENT# ( p , n ) = ( as_int ( p ) , as_int ( n ) ) #NEWLINE# #UNINDENT# except ValueError : #NEWLINE# #INDENT# if all ( ( isinstance ( i , ( SYMPY_INTS , Rational ) ) for i in ( p , n ) ) ) : #NEWLINE# #INDENT# try : #NEWLINE# #INDENT# p = Rational ( p ) #NEWLINE# n = Rational ( n ) #NEWLINE# if ( p . q == 1 ) : #NEWLINE# #INDENT# if ( n . p == 1 ) : #NEWLINE# #INDENT# return ( - multiplicity ( p . p , n . q ) ) #NEWLINE# #UNINDENT# return S . Zero #NEWLINE# #UNINDENT# else : #NEWLINE# #INDENT# if ( p . p == 1 ) : #NEWLINE# #INDENT# return multiplicity ( p . q , n . q ) #NEWLINE# #UNINDENT# else : #NEWLINE# #INDENT# like = min ( multiplicity ( p . p , n . p ) , multiplicity ( p . q , n . q ) ) #NEWLINE# cross = min ( multiplicity ( p . q , n . p ) , multiplicity ( p . p , n . q ) ) #NEWLINE# return ( like - cross ) #NEWLINE# #UNINDENT# #UNINDENT# #UNINDENT# except AttributeError : #NEWLINE# #INDENT# pass #NEWLINE# #UNINDENT# #UNINDENT# raise ValueError ( ( 'expecting ints or fractions, got %s and %s' % ( p , n ) ) ) #NEWLINE# #UNINDENT# if ( n == 0 ) : #NEWLINE# #INDENT# raise ValueError ( ( 'no such integer exists: multiplicity of %s is not-defined' % n ) ) #NEWLINE# #UNINDENT# if ( p == 2 ) : #NEWLINE# #INDENT# return trailing ( n ) #NEWLINE# #UNINDENT# if ( p < 2 ) : #NEWLINE# #INDENT# raise ValueError ( ( 'p must be an integer, 2 or larger, but got %s' % p ) ) #NEWLINE# #UNINDENT# if ( p == n ) : #NEWLINE# #INDENT# return 1 #NEWLINE# #UNINDENT# m = 0 #NEWLINE# ( n , rem ) = divmod ( n , p ) #NEWLINE# while ( not rem ) : #NEWLINE# #INDENT# m += 1 #NEWLINE# if ( m > 5 ) : #NEWLINE# #INDENT# e = 2 #NEWLINE# while 1 : #NEWLINE# #INDENT# ppow = ( p ** e ) #NEWLINE# if ( ppow < n ) : #NEWLINE# #INDENT# ( nnew , rem ) = divmod ( n , ppow ) #NEWLINE# if ( not rem ) : #NEWLINE# #INDENT# m += e #NEWLINE# e *= 2 #NEWLINE# n = nnew #NEWLINE# continue #NEWLINE# #UNINDENT# #UNINDENT# return ( m + multiplicity ( p , n ) ) #NEWLINE# #UNINDENT# #UNINDENT# ( n , rem ) = divmod ( n , p ) #NEWLINE# #UNINDENT# return m