In How hard is it to compute the number of prime factors of a given integer? a question was asked on computing number of prime factors of an integer.
Suppose we have a polynomial $f(X)\in \Bbb Z[X]$ with leading coefficient $1$ and the constant term $1$, there is a polynomial time algorithm in terms of degree and size of coefficients to factor $f(X)=\prod_if_i(X)$ where each $f_i(X)$ is in $\Bbb Z[X]$.
However if I just want to count the number of irreducible factors of $f(X)$, is there a way to do this in polynomial time without factoring the polynomial?
Probably an algorithm to the question: "Given $F(x)\in\Bbb Z[x]$, find maximum $k$ such that $F(x)=f_1(x)^{a_1}\dots f_k(x)^{a_k}$ where $f_i(x)\in\Bbb Z[x]$ has $deg(f_i(x))\geq 1$ and $i\neq j\implies f_i(x)\neq f_j(x)$ with each $a_i > 0$?" is close to the question here.
Atleast can we say $k>1$ without factoring? Or would this also split the polynomial?
