Всем здравствуйте! Никак не получается решить одну задачу.
Условие задачи:
В этой задаче рассматриваются только чётные целые числа. Чётное натуральное число 𝑛
будем называть чётнопростым числом, если его нельзя представить в виде произведения двух чётных чисел. Например, числа 2
и 6
— чётнопростые. Очевидно, что каждое число либо является чётнопростым, либо разлагается в произведение чётнопростых. Но такое разложение на чётнопростые не всегда единственно.
Входные данные:
Дано чётное натуральное 𝑛 ≤ 109
.
Выходные данные:
Если число 𝑛
— чётнопростое, выведите слово prime
. Если это число единственным образом разлагается в произведение двух и более чётнопростых, то выведите слово single
, а в следующей строке выведите разложение этого числа на чётнопростые множители. Если число допускает несколько различных разложений на чётнопростые, то выведите слово many
, а в следующих двух строках выведите два каких-нибудь различных разложения числа на чётнопростые множители. Сложность алгоритма должна быть О(√n)
.
Мой код:
def even_prime_check(n): # проверка числа на чётно-простоту
if n%4 == 0:
return False
else:
return True
def even_prime_factorization(n): # функция для не чётно-простого числа
a = []
b = []
a.append(n//2)
a.append(2)
check1 = a[0]
check2 = a[1]
for d in range(6,10**6,4):
if n%d == 0 and even_prime_check(n//d) and n//d != check2 and d != check1:
b.append(n//d)
b.append(d)
break
return a,b
n = int(input())
a,b = even_prime_factorization(n)
if even_prime_check(n):
print('prime')
elif len(a) == 2 and len(b) == 0:
print('single')
print(' '.join(map(str, a)))
elif len(a) == 2 and len(b) == 2:
print('many')
print(' '.join(map(str, a)))
print(' '.join(map(str, b)))
Я тестирую эту программу, вроде всё верно. Но моё решение засчитывается как неверное. Помогите, пожалуйста, найти ошибку и исправить код.
8
: программа ничего не выводит. По сути,8
— и не чётнопростое, и нет чётнопростых делителей (4
— не чётнопростое). Непонятно, как с этим справится.8 = 2 * 2 * 2
двух и более