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