Решение состоит из двух частей: функция которая составляет словарь простых делителей и их степени, и основной код, который отвечает за вызов этой функции и генерацию строки вывода.
В функции prime_factorization использовался достаточно оптимальный алгоритм факторизации.
Код и примеры работы есть в виде скринов.
Исходный код:
def prime_factorization(n):
d = 2
divisors = {}
while n > 1:
if n % d == 0:
divisors[d] = divisors.get(d, 0) + 1
n //= d
elif d*d > n:
d = n
else:
d += 1
return divisors
if __name__ == '__main__':
n = int(input())
factors = prime_factorization(n)
s = ' * '.join([f'{k}^{v}' for k, v in sorted(factors.items())])
def solve(n):
d = 0
while not (n&1):
d += 1
n //= 2
a = [2]*d
a[-1] *= n
if d == 1:
print("prime")
return
for x in range(3, int(n**.5)+1, 2):
if not (n%x):
b = a[:]
b[-1] //= x
b[-2] *= x
print("many")
print(" ".join(map(str, a)))
print(" ".join(map(str, b)))
return
print("single")
print(" ".join(map(str, a)))
from sys import stdin
for line in stdin:
print("=== " + line.strip() + " ===")
solve(int(line))
Дайте плз 5 звёзд, мне очень не хватает "Лучших ответов"
Примечание:
Использовался ЯП Python, версия 3.8.10.
Решение состоит из двух частей: функция которая составляет словарь простых делителей и их степени, и основной код, который отвечает за вызов этой функции и генерацию строки вывода.
В функции prime_factorization использовался достаточно оптимальный алгоритм факторизации.
Код и примеры работы есть в виде скринов.
Исходный код:
def prime_factorization(n):
d = 2
divisors = {}
while n > 1:
if n % d == 0:
divisors[d] = divisors.get(d, 0) + 1
n //= d
elif d*d > n:
d = n
else:
d += 1
return divisors
if __name__ == '__main__':
n = int(input())
factors = prime_factorization(n)
s = ' * '.join([f'{k}^{v}' for k, v in sorted(factors.items())])
print(s)