Re: New factoring interface

On Fri Jan 5, 2024 at 20:28, Ethan Slota wrote:

I've been using PARI/GP for a while now and it's immensely helpful with my number theory calculations. I also use it a lot for general factorization as it implements algorithms other than ECM and the QS. With factorization, though, there is an issue I run into a lot: I haven't been able to find any way to get an "incremental" factorization.

You have to get a full factorization even if you don't use all of it, which can be a big slowdown. For example, searching for k-almost primes -- without any builtin functions, you'll need to perform a full factorization.

If some looping construct like `foreachfactor(f = n, ...)' existed, you could write a function `is_k_almost_prime` as `(n, k) -> my(count = 0); foreachfactor(f = n, count++; if(count > k, return(0))); 1'. In many cases, it would be faster than `(n, k) -> bigomega(n) == k'.

Furthermore, if this returns an incremental factorization, I think there should be a flag (or a separate function) to enable a sorted result. I would use it mostly for counting factors, so order is not significant... simply run factoring algorithms until you find a factor, return it, and go again.

I know that there is at least some foundation already present for this in GP: set debug to a value >0 and run `factorint' on some number. The factors should just get exposed to the user.

You can use the flag of factorint to skip part of the factorization and return

non-prime factor(s).

Best,

Loïc