NC algorithms are given for determining the number and degrees of the factors, irreducible over the complex numbers ${\bf C}$, of a multivariate polynomial with rational coefficients and for approximating each irreducible factor. NC is the class of functions computable by logspace-uniform boolean circuits of polynomial size and polylogarithmic depth. The measures of size of the input polynomial are its degree, coefficient length, number of variables (d, c, and n, respectively). If n is fixed, we give a deterministic NC algorithm. If the number of variables is not fixed, we give a random (Monte-Carlo) NC algorithm in these input measures to find the number and degree of each irreducible factor. After reducing to the two-variable, square-free case, we apply the classical algebraic geometry fact that the absolute irreducible factors of $(P(z_1 ,z_2 ) = 0)$ correspond to the connected components of the real surface (or complex curve) $P(z_1 ,z_2 ) = 0$ minus its singular points. In finding the number of connected components of the surface $P = 0$, the surface is projected to the the $z_2 $-plane. The singular points of $P(z_1 ,z_2 )$ lie over the projection’s critical values. The inverse image of a grid isolating the critical values in the $z_2 $-plane lifts to a one-dimensional real curve skeleton on the surface $(P = 0)$ whose number of connected components is precisely the number of connected components of $P = 0$ minus its singular points. The connectivity of this curve skeleton is constructed symbolically using Sturm sequences associated with the various polynomials defining these maps. Given the number of irreducible factors and their degrees, the actual factors can be reconstructed using the recent result of Neff [Proceedings of the 31st Annual Symposium on Foundations of Computer Science, pp. 152–162] on finding zeros of one-variable polynomials in NC.