eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

Факторизация

Факторизация

Однажды вечерком к нам в гости зашел математик Петров Н.Н. Он копался в исходниках PGP (version 0.000001) и обнаружил в реализации алгоритма генерации открытого ключа одной очень известной криптографической системы недоработку. Ключ в этой системе является произведением двух больших простых чисел, не равных друг другу. Петров утверждает, что если числа отличаются незначительно, то разложить ключ не представляет труда. Программист, написавший модуль к PGP, при генерации ключа не учел этого, он только проверил, что множители различны. Вам задано число \textbf{n}, представляющее собой произведение двух простых чисел \textbf{p} и \textbf{q}. Ваша задача -- найти эти числа. \InputFile В первой и единственной строке входного файла записано натуральное число \textbf{n} (\textbf{10^98} ≤ \textbf{n} ≤ \textbf{10^102}). \OutputFile \includegraphics{https://static.e-olymp.com/content/39/3995b40544e525d376185586daa9f99a529da162.jpg} Если окажется, что , то выведите в выходной файл строку "\textbf{Impossible}" (без кавычек). В противном случае в первой строке выходного файла выведите меньший множитель, а во второй строке -- больший.
Лимит времени 1 секунда
Лимит использования памяти 64 MiB
Входные данные #1
7934870381945864918905297081473760990739701202397683128574937380029499574504155950432196212581315823
Выходные данные #1
Impossible
Источник Orel STU & Udmurt SU Contest, Petrozavodsk, Thursday, September 1, 2005