Re: [math-fun] Number of factors

Is there any way of counting the number of factors in a big number other than factoring it?

Well, here's a way to do it without factoring (but it's not fast): The number of distinct prime divisors of n is log_2(d) where d is the number of x in {0,1,...,n-1} such that x^2 mod n = x, that is, d is the number of idempotents in Z/(n). --Edwin