Вот для Агарвала-Кули алгоритма понадобился быстрый алгоритм разложения числа на
два взаимнопростых сомножителя.
Можно, конечно, перебирать два множителя, а потом алгоритмом Евклида проверять простые или нет. Только видимо перебирать надо, как по-хитрому
