Задача №112669. Разложение на четнопростые
В этой задаче рассматриваются только четные целые числа.
Четное натуральное число n будем называть четнопростым числом, если его нельзя представить в виде произведения двух четных чисел. Например, числа 2 и 6 — четнопростые.
Очевидно, что каждое число либо является четнопростым, либо разлагается в произведение четнопростых. Но такое разложение на четнопростые не всегда единственно.
Дано четное натуральное n \(\le\) \(10^9\). Если это число — четнопростое, выведите слово prime. Если это число единственным образом разлагается в произведение двух и более четнопростых, то выведите слово single, а в следующей строке выведите разложение этого числа на четнопростые множители. Если число допускает несколько различных разложений на четнопростые, то выведите слово many, а в следующих двух строках выведите два каких-нибудь различных разложения числа на четнопростые множители.
Сложность алгоритма должна быть O(sqrt(\(n\))) .
6
prime
4
single 2 2