[issue40028] Math module method to find prime factors for non-negative int n

[Dennis Sweeney]

Dennis Sweeney <sweeney.dennis650 at gmail.com> added the comment:

For some more ideas for features or APIs, you could look at: https://docs.sympy.org/latest/modules/ntheory.html or http://doc.sagemath.org/html/en/reference/rings_standard/sage/arith/misc.html for an absolute upper bound.

If there's to be a minimal number theory (imath?) module, I would interested in what's below. I'm a math student so perhaps my workload is perhaps not representative of most people (and I can turn to tools like SageMath for most of this), but nonetheless here would be my wishlist for the stdlib.

- prime_factors(n): iterator or tuple of prime factors in multiplicity
- factorization(n): like collections.Counter(prime_factors(n))
- divisors(n): iterator for divisors based on factorization
- is_prime(n, bases=20): do some randomized Miller-Rabin
- crt(moduli, values): Chinese Remainder Theorem
- xgcd(numbers) -> tuple[int, tuple[int]]: use the extended euclidean algorithm to find gcd and Bezout coefficients
- generate_primes(start=2)
- next_prime(n) / prev_prime(n)
- prime_range(a, b)
- is_square(n) (maybe is_nth_power?)
- multiplicity(p, n): maximal r such that p**r divides n
- is_quadratic_residue(a, modulus)
- primitive_root(modulus)
- multinomial(n, *ks)

Already in math module:
- gcd and lcm 
- comb(n, k)
- perm(n, k)
- isqrt(n)
- factorial(n)

Looking at this list though, I realize that there is infinite potential for feature-creep, and so it would be nice to have an explicit set of guidelines for what sorts of functions are allowed. Perhaps something like "must have a common-enough use case outside of pure math". There's also a limitless amount of micro-optimization that can come with several of these (is_prime, is_square, generate_primes, etc.), so it might be nice to have a guideline about only accepting performace optimizations if the cost in complexity is small.

----------
nosy: +Dennis Sweeney

_______________________________________
Python tracker <report at bugs.python.org>
<https://bugs.python.org/issue40028>
_______________________________________