Repository: sympy/sympy
Pull request: ntheory : Add functionality to return list of all factors
Passing in the argument `multiple=True` to `factorint()` or `factorrat()` returns a list of all the prime factors constituting the number along with multiplicity.

PR #12124 got messed up, so I opened a new PR.
Example:
```
>>> factorint(222,multiple=True)
[2, 3, 37]
>>>factorrat(S(25)/14, multiple=True)
[1/2, 5, 5, 1/7]
```
Fixes #12101 

<!-- If this pull request fixes an issue please indicate which issue by typing "Fixes #NNNN" below.>
Fixes #12101 

Problem statement:
List of prime factors including multiplicity is missing
The vast majority of the time when using prime factorization in algorithms I'm interested in a list of prime factors. E.g. for 24 it's `[2, 2, 2, 3]`. However sympy (to my knowledge) only provides `sympy.factorint` which returns a dictionary. I always end up writing a helper function:

    factorlist = lambda fac: sum(([p] * fac[p] for p in sorted(fac)), [])

It would be really nice if factorizations in this format were directly provided by sympy, either by an option to `factorint` (e.g. `sympy.factorint(24, aslist=True)`) or under a new function name entirely.

Hints from issue discussion:
A possibility is:

```
>>> from sympy.utilities.iterables import multiset_combinations
>>> d={'a':3,'b':2,'c':2}
>>> list(multiset_combinations(d, sum(d.values())))[0]
['a', 'a', 'a', 'b', 'b', 'c', 'c']
>>> d = factoring(24)
>>> list(multiset_combinations(d, sum(d.values())))[0]
[2, 2, 2, 3]
```

But maybe an argument `multiple=True` for `factorint` would be preferable.
@smichr `multiple=True`  for `factorint` is definitely better than my suggestion. I really do think that providing this functionality straight up without a helper function is an improvement for sympy.

Commit message: ntheory: Add multiple=True to return list of factors

Patch to review:
diff --git a/sympy/ntheory/factor_.py b/sympy/ntheory/factor_.py
index 67c2c18ce7db..fe078c375fb4 100644
--- a/sympy/ntheory/factor_.py
+++ b/sympy/ntheory/factor_.py
@@ -803,7 +803,7 @@ def done(n, d):
 
 
 def factorint(n, limit=None, use_trial=True, use_rho=True, use_pm1=True,
-              verbose=False, visual=None):
+              verbose=False, visual=None, multiple=False):
     r"""
     Given a positive integer ``n``, ``factorint(n)`` returns a dict containing
     the prime factors of ``n`` as keys and their respective multiplicities
@@ -942,6 +942,15 @@ def factorint(n, limit=None, use_trial=True, use_rho=True, use_pm1=True,
     smoothness, smoothness_p, divisors
 
     """
+    if multiple:
+        fac = factorint(n, limit=limit, use_trial=use_trial,
+                           use_rho=use_rho, use_pm1=use_pm1,
+                           verbose=verbose, visual=False, multiple=False)
+        factorlist = sum(([p] * fac[p]
+                         if fac[p] > 0 else [S(1)/p]*(-1 * fac[p])
+                         for p in sorted(fac)), [])
+        return factorlist
+
     factordict = {}
     if visual and not isinstance(n, Mul) and not isinstance(n, dict):
         factordict = factorint(n, limit=limit, use_trial=use_trial,
@@ -1172,7 +1181,7 @@ def factorint(n, limit=None, use_trial=True, use_rho=True, use_pm1=True,
 
 
 def factorrat(rat, limit=None, use_trial=True, use_rho=True, use_pm1=True,
-              verbose=False, visual=None):
+              verbose=False, visual=None, multiple=False):
     r"""
     Given a Rational ``r``, ``factorrat(r)`` returns a dict containing
     the prime factors of ``r`` as keys and their respective multiplicities
@@ -1196,6 +1205,15 @@ def factorrat(rat, limit=None, use_trial=True, use_rho=True, use_pm1=True,
         - ``visual``: Toggle product form of output
     """
     from collections import defaultdict
+    if multiple:
+        fac = factorrat(rat, limit=limit, use_trial=use_trial,
+                  use_rho=use_rho, use_pm1=use_pm1,
+                  verbose=verbose, visual=False,multiple=False)
+        factorlist = sum(([p] * fac[p]
+                         if fac[p] > 0 else [S(1)/p]*(-1 * fac[p])
+                         for p in sorted(fac)), [])
+        return factorlist
+
     f = factorint(rat.p, limit=limit, use_trial=use_trial,
                   use_rho=use_rho, use_pm1=use_pm1,
                   verbose=verbose).copy()
diff --git a/sympy/ntheory/tests/test_factor_.py b/sympy/ntheory/tests/test_factor_.py
index aed3766babaf..5fede7819c56 100644
--- a/sympy/ntheory/tests/test_factor_.py
+++ b/sympy/ntheory/tests/test_factor_.py
@@ -154,6 +154,20 @@ def test_factorint():
     assert factorint(5951757) == {3: 1, 7: 1, 29: 2, 337: 1}
     assert factorint(64015937) == {7993: 1, 8009: 1}
     assert factorint(2**(2**6) + 1) == {274177: 1, 67280421310721: 1}
+
+    assert factorint(0, multiple=True) == [0]
+    assert factorint(1, multiple=True) == []
+    assert factorint(-1, multiple=True) == [-1]
+    assert factorint(-2, multiple=True) == [-1, 2]
+    assert factorint(-16, multiple=True) == [-1, 2, 2, 2, 2]
+    assert factorint(2, multiple=True) == [2]
+    assert factorint(24, multiple=True) == [2, 2, 2, 3]
+    assert factorint(126, multiple=True) == [2, 3, 3, 7]
+    assert factorint(123456, multiple=True) == [2, 2, 2, 2, 2, 2, 3, 643]
+    assert factorint(5951757, multiple=True) == [3, 7, 29, 29, 337]
+    assert factorint(64015937, multiple=True) == [7993, 8009]
+    assert factorint(2**(2**6) + 1, multiple=True) == [274177, 67280421310721]
+
     assert multiproduct(factorint(fac(200))) == fac(200)
     for b, e in factorint(fac(150)).items():
         assert e == fac_multiplicity(150, b)
@@ -424,6 +438,13 @@ def test_factorrat():
     assert str(factorrat(S(25)/14, visual=True)) == '5**2/(2*7)'
     assert str(factorrat(S(-25)/14/9, visual=True)) == '-5**2/(2*3**2*7)'
 
+    assert factorrat(S(12)/1, multiple=True) == [2, 2, 3]
+    assert factorrat(S(1)/1, multiple=True) == []
+    assert factorrat(S(25)/14, multiple=True) == [1/2, 5, 5, 1/7]
+    assert factorrat(S(12)/1, multiple=True) == [2, 2, 3]
+    assert factorrat(S(-25)/14/9, multiple=True) == \
+        [-1, 1/2, 1/3, 1/3, 5, 5, 1/7]
+
 
 def test_visual_io():
     sm = smoothness_p


Code review comments:
diff_hunk: @@ -942,6 +942,15 @@ def factorint(n, limit=None, use_trial=True, use_rho=True, use_pm1=True,
     smoothness, smoothness_p, divisors
 
     """
+    if multiple:
+        fac = factorint(n, limit=limit, use_trial=use_trial,
+                           use_rho=use_rho, use_pm1=use_pm1,
+                           verbose=verbose, visual=False, multiple=False)
+        factorlist = sum(([p] * fac[p]
+                         if fac[p] > 0 else [S(1)/p]*(-1 * fac[p])
+                         for p in sorted(fac)), [])
path: sympy/ntheory/factor_.py
text: @user1:
instead of straight sorting, perhaps `for p, _ in sorted(fac.items(), key=lambda (p, m): p if m > 0 else 1/p)` would be better so you would get `[1/7, 1/2, 5, 5]` for `factorrat(S(25)/14, multiple=True)` instead of `[1/2, 5, 5, 1/7]`.