https://github.com/python/cpython/commit/9120450b253a718ae295d7e86b5087705c1... commit: 9120450b253a718ae295d7e86b5087705c177eae branch: 3.11 author: Miss Islington (bot) <31488909+miss-islington@users.noreply.github.com> committer: miss-islington <31488909+miss-islington@users.noreply.github.com> date: 2022-12-28T12:37:58-08:00 summary: Restore early-out to factor(). Strengthen tests. (GH-100591) (cherry picked from commit c4c5790120beabed83ce5855f18d209ab8324434) Co-authored-by: Raymond Hettinger <rhettinger@users.noreply.github.com> files: M Doc/library/itertools.rst diff --git a/Doc/library/itertools.rst b/Doc/library/itertools.rst index 221863cbbcc5..93bc1f792f54 100644 --- a/Doc/library/itertools.rst +++ b/Doc/library/itertools.rst @@ -862,12 +862,14 @@ which incur interpreter overhead. "Prime factors of n." # factor(99) --> 3 3 11 for prime in sieve(math.isqrt(n) + 1): - while n >= prime: + while True: quotient, remainder = divmod(n, prime) if remainder: break yield prime n = quotient + if n == 1: + return if n >= 2: yield n @@ -1256,13 +1258,21 @@ which incur interpreter overhead. [3, 3] >>> list(factor(10)) [2, 5] - >>> list(factor(999953*999983)) + >>> list(factor(128_884_753_939)) # large prime + [128884753939] + >>> list(factor(999953 * 999983)) # large semiprime [999953, 999983] - >>> all(math.prod(factor(n)) == n for n in range(1, 1000)) + >>> list(factor(6 ** 20)) == [2] * 20 + [3] * 20 # large power + True + >>> list(factor(909_909_090_909)) # large multiterm composite + [3, 3, 7, 13, 13, 751, 113797] + >>> math.prod([3, 3, 7, 13, 13, 751, 113797]) + 909909090909 + >>> all(math.prod(factor(n)) == n for n in range(1, 2_000)) True - >>> all(set(factor(n)) <= set(sieve(n+1)) for n in range(1, 1000)) + >>> all(set(factor(n)) <= set(sieve(n+1)) for n in range(2_000)) True - >>> all(list(factor(n)) == sorted(factor(n)) for n in range(1, 1000)) + >>> all(list(factor(n)) == sorted(factor(n)) for n in range(2_000)) True >>> list(flatten([('a', 'b'), (), ('c', 'd', 'e'), ('f',), ('g', 'h', 'i')]))