Задача Ейлера

У цій задачі ми згадаємо великого математика Леонарда Ейлера ($1707$–$1783$) і дослідимо його добре відому функцію $\varphi (n)$.

Значення $\varphi (n)$ для натурального числа $n$ визначається як кількість цілих чисел k~(1 \le k \le n), взаємно простих з $n$. Два натуральні числа називаються взаємно простими, якщо їх найбільший спільний дільник дорівнює $1$. Наприклад, \phi(6) = 2, оскільки тільки числа $1$ і $5$ взаємно прості з $6$, тоді як $2$, $3$, $4$ і $6$ — ні.

Задача Ейлера формулюється наступним чином: за даним натуральним числом $n$ знайдіть усі такі натуральні числа $x$, для яких виконується рівність \phi(x) = n.