Решение простой версии не помогает решать сложную. В описанном ниже решении нам придётся сделать почти $1000$ запросов.

Выберем числа $m_1$ и $m_2$, такие что $\gcd(m_1, m_2) = 1$, а $m_1 \cdot m_2 \ge 10^6$. Как их выбрать узнаем чуть позже. Проверим, является ли $p$ делителем $m_1$ или $m_2$. Для этого спросим все простые делители $m_1$ с модулем $m_1$ и все простые делители $m_2$ с модулем $m_2$. Если угадали, выводим ответ.

Пусть мы знаем, что $p \equiv d_1 \mod m_1$ и $p \equiv d_2 \mod m_2$. В таком случае можно применить КТО (Китайскую теорему об остатках) и найти $p$. Чтобы узнать $d_1$ надо перебрать все числа, меньшие $m_1$ и взаимно простые с ним. Этого достаточно, так как в противном случае $p$ имело бы нетривиальный делитель. Аналогично можно найти $d_2$.

Остаётся вопрос как выбрать $m_1$ и $m_2$. Нужно чтобы $\varphi(m_1) + \varphi(m_2) + \varepsilon \le 1000$, где $\varphi$ это функция Эйлера, а $\varepsilon$ это суммарное количество простых делителей $m_1$, $m_2$ и вывод ответа. Прекальком можно найти подходящую пару чисел, например, $m_1 = 1155$, $m_2 = 1118$.
