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