Algorithm for finding prime numbers of specific form Given the natural number $n$,who is in the form $p^2 \cdot q^2$,with $p$,$q$ prime numbers.Also $φ(n)$ is given.Describe a fast algorithm(polynomial time) that calculates the $p$ and $q$.Apply your algorithm to calculate the $p$,$q$ when $n=34969$ and $φ(n)=29920$
I found this problem on a mathematical competition on cryptography.I  tried to find a solution alone and in the internet and i didn't conclude anywhere, can we find a solution?
 A: Hint: 
$$\phi(n) = n^2 - n(p+q) - pq$$
A: Since $n$ is a perfect square, $pq = \sqrt{n}$. Now, as for the $\phi$ function:
$$ \phi(p^2 q^2) = \phi(p^2)\phi(q^2) = (p - 1)(q - 1)pq$$
Thus, $$\dfrac{\phi(n)}{\sqrt{n}} = (p - 1)(q - 1) = pq - p - q + 1$$
And thus, you get:
$$\sqrt{n} - \dfrac{\phi(n)}{\sqrt{n}} + 1= p + q = p + \dfrac{\sqrt{n}}{p}$$
Multiply both sides by $-p$:
$$p^2 - p\left(\sqrt{n} - \dfrac{\phi(n)}{\sqrt{n}} + 1\right) + \sqrt{n} = 0$$
Let's try your example. Since $n = 34969$ and $\phi(n) = 29920$, then $\sqrt{n} = 187$ and the equation we have to solve for $p$ is:
$$p^2 - p\left(187 - \dfrac{29920}{187} + 1\right) + 187 = 0$$
If we simplify:
$$p^2 - 28p + 187 = 0$$
The solutions are $p = 11$ and $p = 17$. Actually, due to the symmetric relation between $p$ and $q$ in our previous equation, these two solutions for $p$ happen to be the solution for the pair $(p, q)$. You'd notice that $pq = 187$ if we assign $p = 11$ and $q = 17$.  
So, an efficient algorithm is to solve the quadratic equation. The solution for the pair $(p, q)$ is then just both roots of the equation. This is $\mathcal{O}(1)$.
