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?
1
-
$\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
Add a comment
|
$\begingroup$
$\endgroup$
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.
$\begingroup$
$\endgroup$
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.
answered Jul 1 '16 at 17:48
