#NEWLINE# def factorint( n , limit = None , use_trial = True , use_rho = True , use_pm1 = True , verbose = False , visual = None ) : #NEWLINE# #INDENT# "\n    Given a positive integer ``n``, ``factorint(n)`` returns a dict containing\n    the prime factors of ``n`` as keys and their respective multiplicities\n    as values. For example:\n\n    >>> from sympy.ntheory import factorint\n    >>> factorint(2000)    # 2000 = (2**4) * (5**3)\n    {2: 4, 5: 3}\n    >>> factorint(65537)   # This number is prime\n    {65537: 1}\n\n    For input less than 2, factorint behaves as follows:\n\n        - ``factorint(1)`` returns the empty factorization, ``{}``\n        - ``factorint(0)`` returns ``{0:1}``\n        - ``factorint(-n)`` adds ``-1:1`` to the factors and then factors ``n``\n\n    Partial Factorization:\n\n    If ``limit`` (> 3) is specified, the search is stopped after performing\n    trial division up to (and including) the limit (or taking a\n    corresponding number of rho/p-1 steps). This is useful if one has\n    a large number and only is interested in finding small factors (if\n    any). Note that setting a limit does not prevent larger factors\n    from being found early; it simply means that the largest factor may\n    be composite. Since checking for perfect power is relatively cheap, it is\n    done regardless of the limit setting.\n\n    This number, for example, has two small factors and a huge\n    semi-prime factor that cannot be reduced easily:\n\n    >>> from sympy.ntheory import isprime\n    >>> from sympy.core.compatibility import long\n    >>> a = 1407633717262338957430697921446883\n    >>> f = factorint(a, limit=10000)\n    >>> f == {991: 1, long(202916782076162456022877024859): 1, 7: 1}\n    True\n    >>> isprime(max(f))\n    False\n\n    This number has a small factor and a residual perfect power whose\n    base is greater than the limit:\n\n    >>> factorint(3*101**7, limit=5)\n    {3: 1, 101: 7}\n\n    Visual Factorization:\n\n    If ``visual`` is set to ``True``, then it will return a visual\n    factorization of the integer.  For example:\n\n    >>> from sympy import pprint\n    >>> pprint(factorint(4200, visual=True))\n     3  1  2  1\n    2 *3 *5 *7\n\n    Note that this is achieved by using the evaluate=False flag in Mul\n    and Pow. If you do other manipulations with an expression where\n    evaluate=False, it may evaluate.  Therefore, you should use the\n    visual option only for visualization, and use the normal dictionary\n    returned by visual=False if you want to perform operations on the\n    factors.\n\n    You can easily switch between the two forms by sending them back to\n    factorint:\n\n    >>> from sympy import Mul, Pow\n    >>> regular = factorint(1764); regular\n    {2: 2, 3: 2, 7: 2}\n    >>> pprint(factorint(regular))\n     2  2  2\n    2 *3 *7\n\n    >>> visual = factorint(1764, visual=True); pprint(visual)\n     2  2  2\n    2 *3 *7\n    >>> print(factorint(visual))\n    {2: 2, 3: 2, 7: 2}\n\n    If you want to send a number to be factored in a partially factored form\n    you can do so with a dictionary or unevaluated expression:\n\n    >>> factorint(factorint({4: 2, 12: 3})) # twice to toggle to dict form\n    {2: 10, 3: 3}\n    >>> factorint(Mul(4, 12, evaluate=False))\n    {2: 4, 3: 1}\n\n    The table of the output logic is:\n\n        ====== ====== ======= =======\n                       Visual\n        ------ ----------------------\n        Input  True   False   other\n        ====== ====== ======= =======\n        dict    mul    dict    mul\n        n       mul    dict    dict\n        mul     mul    dict    dict\n        ====== ====== ======= =======\n\n    Notes\n    =====\n\n    Algorithm:\n\n    The function switches between multiple algorithms. Trial division\n    quickly finds small factors (of the order 1-5 digits), and finds\n    all large factors if given enough time. The Pollard rho and p-1\n    algorithms are used to find large factors ahead of time; they\n    will often find factors of the order of 10 digits within a few\n    seconds:\n\n    >>> factors = factorint(12345678910111213141516)\n    >>> for base, exp in sorted(factors.items()):\n    ...     print('%s %s' % (base, exp))\n    ...\n    2 2\n    2507191691 1\n    1231026625769 1\n\n    Any of these methods can optionally be disabled with the following\n    boolean parameters:\n\n        - ``use_trial``: Toggle use of trial division\n        - ``use_rho``: Toggle use of Pollard's rho method\n        - ``use_pm1``: Toggle use of Pollard's p-1 method\n\n    ``factorint`` also periodically checks if the remaining part is\n    a prime number or a perfect power, and in those cases stops.\n\n\n    If ``verbose`` is set to ``True``, detailed progress is printed.\n\n    See Also\n    ========\n\n    smoothness, smoothness_p, divisors\n\n    " #NEWLINE# factordict = { #NEWLINE# #INDENT# #NEWLINE# #UNINDENT# } #NEWLINE# if ( visual and ( not isinstance ( n , Mul ) ) and ( not isinstance ( n , dict ) ) ) : #NEWLINE# #INDENT# factordict = factorint ( n , limit = limit , use_trial = use_trial , use_rho = use_rho , use_pm1 = use_pm1 , verbose = verbose , visual = False ) #NEWLINE# #UNINDENT# else : #NEWLINE# #INDENT# if isinstance ( n , Mul ) : #NEWLINE# #INDENT# factordict = dict ( [ ( int ( k ) , int ( v ) ) for ( k , v ) in list ( n . as_powers_dict ( ) . items ( ) ) ] ) #NEWLINE# #UNINDENT# else : #NEWLINE# #INDENT# if isinstance ( n , dict ) : #NEWLINE# #INDENT# factordict = n #NEWLINE# #UNINDENT# #UNINDENT# #UNINDENT# if ( factordict and ( isinstance ( n , Mul ) or isinstance ( n , dict ) ) ) : #NEWLINE# #INDENT# for k in list ( factordict . keys ( ) ) : #NEWLINE# #INDENT# if isprime ( k ) : #NEWLINE# #INDENT# continue #NEWLINE# #UNINDENT# e = factordict . pop ( k ) #NEWLINE# d = factorint ( k , limit = limit , use_trial = use_trial , use_rho = use_rho , use_pm1 = use_pm1 , verbose = verbose , visual = False ) #NEWLINE# for ( k , v ) in d . items ( ) : #NEWLINE# #INDENT# if ( k in factordict ) : #NEWLINE# #INDENT# factordict [ k ] += ( v * e ) #NEWLINE# #UNINDENT# else : #NEWLINE# #INDENT# factordict [ k ] = ( v * e ) #NEWLINE# #UNINDENT# #UNINDENT# #UNINDENT# #UNINDENT# if ( visual or ( ( type ( n ) is dict ) and ( visual is not True ) and ( visual is not False ) ) ) : #NEWLINE# #INDENT# if ( factordict == { #NEWLINE# #INDENT# #NEWLINE# #UNINDENT# } ) : #NEWLINE# #INDENT# return S . One #NEWLINE# #UNINDENT# if ( ( - 1 ) in factordict ) : #NEWLINE# #INDENT# factordict . pop ( ( - 1 ) ) #NEWLINE# args = [ S . NegativeOne ] #NEWLINE# #UNINDENT# else : #NEWLINE# #INDENT# args = [ ] #NEWLINE# #UNINDENT# args . extend ( [ Pow ( * i , evaluate = False ) for i in sorted ( factordict . items ( ) ) ] ) #NEWLINE# return Mul ( * args , evaluate = False ) #NEWLINE# #UNINDENT# else : #NEWLINE# #INDENT# if ( isinstance ( n , dict ) or isinstance ( n , Mul ) ) : #NEWLINE# #INDENT# return factordict #NEWLINE# #UNINDENT# #UNINDENT# assert ( use_trial or use_rho or use_pm1 ) #NEWLINE# n = as_int ( n ) #NEWLINE# if limit : #NEWLINE# #INDENT# limit = int ( limit ) #NEWLINE# #UNINDENT# if ( n < 0 ) : #NEWLINE# #INDENT# factors = factorint ( ( - n ) , limit = limit , use_trial = use_trial , use_rho = use_rho , use_pm1 = use_pm1 , verbose = verbose , visual = False ) #NEWLINE# factors [ ( - 1 ) ] = 1 #NEWLINE# return factors #NEWLINE# #UNINDENT# if ( limit and ( limit < 2 ) ) : #NEWLINE# #INDENT# if ( n == 1 ) : #NEWLINE# #INDENT# return { #NEWLINE# #INDENT# #NEWLINE# #UNINDENT# } #NEWLINE# #UNINDENT# return { #NEWLINE# #INDENT# n : 1 , #NEWLINE# #UNINDENT# } #NEWLINE# #UNINDENT# else : #NEWLINE# #INDENT# if ( n < 10 ) : #NEWLINE# #INDENT# return [ { #NEWLINE# #INDENT# 0 : 1 , #NEWLINE# #UNINDENT# } , { #NEWLINE# #INDENT# #NEWLINE# #UNINDENT# } , { #NEWLINE# #INDENT# 2 : 1 , #NEWLINE# #UNINDENT# } , { #NEWLINE# #INDENT# 3 : 1 , #NEWLINE# #UNINDENT# } , { #NEWLINE# #INDENT# 2 : 2 , #NEWLINE# #UNINDENT# } , { #NEWLINE# #INDENT# 5 : 1 , #NEWLINE# #UNINDENT# } , { #NEWLINE# #INDENT# 2 : 1 , #NEWLINE# 3 : 1 , #NEWLINE# #UNINDENT# } , { #NEWLINE# #INDENT# 7 : 1 , #NEWLINE# #UNINDENT# } , { #NEWLINE# #INDENT# 2 : 3 , #NEWLINE# #UNINDENT# } , { #NEWLINE# #INDENT# 3 : 2 , #NEWLINE# #UNINDENT# } ] [ n ] #NEWLINE# #UNINDENT# #UNINDENT# factors = { #NEWLINE# #INDENT# #NEWLINE# #UNINDENT# } #NEWLINE# if verbose : #NEWLINE# #INDENT# sn = str ( n ) #NEWLINE# if ( len ( sn ) > 50 ) : #NEWLINE# #INDENT# print ( ( ( ( 'Factoring %s' % sn [ : 5 ] ) + ( '..(%i other digits)..' % ( len ( sn ) - 10 ) ) ) + sn [ ( - 5 ) : ] ) ) #NEWLINE# #UNINDENT# else : #NEWLINE# #INDENT# print ( 'Factoring' , n ) #NEWLINE# #UNINDENT# #UNINDENT# if use_trial : #NEWLINE# #INDENT# small = ( 2 ** 15 ) #NEWLINE# fail_max = 600 #NEWLINE# small = min ( small , ( limit or small ) ) #NEWLINE# if verbose : #NEWLINE# #INDENT# print ( ( trial_int_msg % ( 2 , small , fail_max ) ) ) #NEWLINE# #UNINDENT# ( n , next_p ) = _factorint_small ( factors , n , small , fail_max ) #NEWLINE# #UNINDENT# else : #NEWLINE# #INDENT# next_p = 2 #NEWLINE# #UNINDENT# if ( factors and verbose ) : #NEWLINE# #INDENT# for k in sorted ( factors ) : #NEWLINE# #INDENT# print ( ( factor_msg % ( k , factors [ k ] ) ) ) #NEWLINE# #UNINDENT# #UNINDENT# if ( next_p == 0 ) : #NEWLINE# #INDENT# if ( n > 1 ) : #NEWLINE# #INDENT# factors [ int ( n ) ] = 1 #NEWLINE# #UNINDENT# if verbose : #NEWLINE# #INDENT# print ( complete_msg ) #NEWLINE# #UNINDENT# return factors #NEWLINE# #UNINDENT# try : #NEWLINE# #INDENT# if ( limit and ( next_p > limit ) ) : #NEWLINE# #INDENT# if verbose : #NEWLINE# #INDENT# print ( 'Exceeded limit:' , limit ) #NEWLINE# #UNINDENT# _check_termination ( factors , n , limit , use_trial , use_rho , use_pm1 , verbose ) #NEWLINE# if ( n > 1 ) : #NEWLINE# #INDENT# factors [ int ( n ) ] = 1 #NEWLINE# #UNINDENT# return factors #NEWLINE# #UNINDENT# else : #NEWLINE# #INDENT# sqrt_n = integer_nthroot ( n , 2 ) [ 0 ] #NEWLINE# a = ( sqrt_n + 1 ) #NEWLINE# a2 = ( a ** 2 ) #NEWLINE# b2 = ( a2 - n ) #NEWLINE# for i in range ( 3 ) : #NEWLINE# #INDENT# ( b , fermat ) = integer_nthroot ( b2 , 2 ) #NEWLINE# if fermat : #NEWLINE# #INDENT# break #NEWLINE# #UNINDENT# b2 += ( ( 2 * a ) + 1 ) #NEWLINE# a += 1 #NEWLINE# #UNINDENT# if fermat : #NEWLINE# #INDENT# if verbose : #NEWLINE# #INDENT# print ( fermat_msg ) #NEWLINE# #UNINDENT# if limit : #NEWLINE# #INDENT# limit -= 1 #NEWLINE# #UNINDENT# for r in [ ( a - b ) , ( a + b ) ] : #NEWLINE# #INDENT# facs = factorint ( r , limit = limit , use_trial = use_trial , use_rho = use_rho , use_pm1 = use_pm1 , verbose = verbose ) #NEWLINE# factors . update ( facs ) #NEWLINE# #UNINDENT# raise StopIteration #NEWLINE# #UNINDENT# _check_termination ( factors , n , limit , use_trial , use_rho , use_pm1 , verbose ) #NEWLINE# #UNINDENT# #UNINDENT# except StopIteration : #NEWLINE# #INDENT# if verbose : #NEWLINE# #INDENT# print ( complete_msg ) #NEWLINE# #UNINDENT# return factors #NEWLINE# #UNINDENT# ( low , high ) = ( next_p , ( 2 * next_p ) ) #NEWLINE# limit = ( limit or sqrt_n ) #NEWLINE# limit += 1 #NEWLINE# while 1 : #NEWLINE# #INDENT# try : #NEWLINE# #INDENT# high_ = high #NEWLINE# if ( limit < high_ ) : #NEWLINE# #INDENT# high_ = limit #NEWLINE# #UNINDENT# if use_trial : #NEWLINE# #INDENT# if verbose : #NEWLINE# #INDENT# print ( ( trial_msg % ( low , high_ ) ) ) #NEWLINE# #UNINDENT# ps = sieve . primerange ( low , high_ ) #NEWLINE# ( n , found_trial ) = _trial ( factors , n , ps , verbose ) #NEWLINE# if found_trial : #NEWLINE# #INDENT# _check_termination ( factors , n , limit , use_trial , use_rho , use_pm1 , verbose ) #NEWLINE# #UNINDENT# #UNINDENT# else : #NEWLINE# #INDENT# found_trial = False #NEWLINE# #UNINDENT# if ( high > limit ) : #NEWLINE# #INDENT# if verbose : #NEWLINE# #INDENT# print ( 'Exceeded limit:' , limit ) #NEWLINE# #UNINDENT# if ( n > 1 ) : #NEWLINE# #INDENT# factors [ int ( n ) ] = 1 #NEWLINE# #UNINDENT# raise StopIteration #NEWLINE# #UNINDENT# if ( not found_trial ) : #NEWLINE# #INDENT# if ( use_pm1 or use_rho ) : #NEWLINE# #INDENT# high_root = max ( int ( math . log ( ( high_ ** 0.7 ) ) ) , low , 3 ) #NEWLINE# if use_pm1 : #NEWLINE# #INDENT# if verbose : #NEWLINE# #INDENT# print ( ( pm1_msg % ( high_root , high_ ) ) ) #NEWLINE# #UNINDENT# c = pollard_pm1 ( n , B = high_root , seed = high_ ) #NEWLINE# if c : #NEWLINE# #INDENT# ps = factorint ( c , limit = ( limit - 1 ) , use_trial = use_trial , use_rho = use_rho , use_pm1 = use_pm1 , verbose = verbose ) #NEWLINE# ( n , _ ) = _trial ( factors , n , ps , verbose = False ) #NEWLINE# _check_termination ( factors , n , limit , use_trial , use_rho , use_pm1 , verbose ) #NEWLINE# #UNINDENT# #UNINDENT# if use_rho : #NEWLINE# #INDENT# max_steps = high_root #NEWLINE# if verbose : #NEWLINE# #INDENT# print ( ( rho_msg % ( 1 , max_steps , high_ ) ) ) #NEWLINE# #UNINDENT# c = pollard_rho ( n , retries = 1 , max_steps = max_steps , seed = high_ ) #NEWLINE# if c : #NEWLINE# #INDENT# ps = factorint ( c , limit = ( limit - 1 ) , use_trial = use_trial , use_rho = use_rho , use_pm1 = use_pm1 , verbose = verbose ) #NEWLINE# ( n , _ ) = _trial ( factors , n , ps , verbose = False ) #NEWLINE# _check_termination ( factors , n , limit , use_trial , use_rho , use_pm1 , verbose ) #NEWLINE# #UNINDENT# #UNINDENT# #UNINDENT# #UNINDENT# #UNINDENT# except StopIteration : #NEWLINE# #INDENT# if verbose : #NEWLINE# #INDENT# print ( complete_msg ) #NEWLINE# #UNINDENT# return factors #NEWLINE# #UNINDENT# ( low , high ) = ( high , ( high * 2 ) )