0
$\begingroup$

I came upon this question when I was trying to look for a general computer approach (better than a brute force approach) to solve the equation, $\\ \phi(n) = k$ for any given $k$. It could be made a lot faster if there was an easy and efficient way to determine the number of distinct prime factors a number has. Does anyone know if there is a function in number theory that does this, and if there is, what is the most efficient way to calculate it?

$\endgroup$
  • $\begingroup$ There is a polynomial time primality testing algorithm. Perhaps there is a polynomial time algorithm for your generalization of primality testing. $\endgroup$ – André Nicolas Jul 1 '16 at 18:31
1
$\begingroup$

No, there is no known such computable function as the numbers get sufficiently large. For example, it's unknown how many prime factors googolplex+1 has, but it's over 14.

$\endgroup$
0
$\begingroup$

There are many algorithms on integer factorization, but they do not run in polynomial time (only sub-exponential time). So it is possible to determine the number of prime divisors of integers $n$ for a "reasonable size" on $n$. On the other hand, there is a lot known about solving the equation $\phi(n)=k$, where we do not need to know the number of prime divisors of $n$, e.g., see this question and the references given.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.