Question

ЯЗЫК ПИТОН!! 1) Дано натуральное число N>1. Выведите все его простые натуральные делители с учетом кратности. Алгоритм должен иметь сложность O(n−−√). Входные данные Вводится натуральное число N≤2∗109. Выходные данные Выведите ответ на задачу. 2)Количество всех натуральных делителей натурального числа n обозначается τ(n). Сумма всех натуральных делителей числа n обозначается σ(n). Входные данные Дано натуральное n≤109. Выходные данные Выведите τ(n) и σ(n). Примечание Сложность алгоритма должна быть O(n−−√). 3)Два различных числа n и m называются дружественными, если сумма делителей числа n (включая 1, но исключая само n) равна числу m и наоборот. Например, 220 и 284 – дружественные числа. Входные данные Дано число k≤50000 Выходные данные Выведите все пары дружественных чисел, каждое из которых не превосходит k. Пары необходимо выводить по одной в строке, разделяя числа в паре пробелом. Каждая пара должна быть выведена только один раз (перестановка чисел новую пару не дает).

Answer 1

Ответ:

1)

n = int(input())

ans = []

for i in range(int(n ** 0.5 + 1)):

if n % i == 0:

ans.append(i)

print(*ans)

2)

x = int(input())

a = 0

d = 2  

s = int(x/2) + 1

for i in range(2, s):  

   if x % i == 0:

       d += 1

       a += i

print(d, x + 1 + a)

3)

k = 10000

ans = {}

   

def d(number):

   return sum(x for x in range(1, (number // 2) + 1) if number % x == 0)

   

for i in range(1, k+1):

   a = d(i)

   if i == d(a) and i != a:

       if i and a not in pairs:

           pairs[i] = a

print(pairs)

Answer 2

1. Для поиска всех простых натуральных делителей числа N с учетом кратности и при условии сложности O(√n), вы можете использовать следующий код на языке Python:

pythonCopy code
import math

def prime_factors(n):
    factors = []
    while n % 2 == 0:
        factors.append(2)
        n //= 2
    for i in range(3, int(math.sqrt(n)) + 1, 2):
        while n % i == 0:
            factors.append(i)
            n //= i
    if n > 1:
        factors.append(n)
    return factors

N = int(input())
factors = prime_factors(N)
for factor in factors:
    print(factor)

2. Для вычисления τ(n) и σ(n) с сложностью O(√n), вы можете использовать следующий код:

pythonCopy code
import math

def tau_sigma(n):
    tau = 1
    sigma = 1
    for i in range(2, int(math.sqrt(n)) + 1):
        if n % i == 0:
            count = 0
            while n % i == 0:
                n //= i
                count += 1
            tau *= (count + 1)
            sigma *= (i**(count + 1) - 1) // (i - 1)
    if n > 1:
        tau *= 2
        sigma *= (n + 1)
    return tau, sigma

n = int(input())
tau, sigma = tau_sigma(n)
print(tau, sigma)

3. Для поиска дружественных чисел суммарной сложностью O(k√k), вы можете использовать следующий код:

pythonCopy code
def sum_of_divisors(n):
    divisors_sum = [0] * (n + 1)
    for i in range(1, n + 1):
        for j in range(i * 2, n + 1, i):
            divisors_sum[j] += i
    return divisors_sum

k = int(input())
divisor_sums = sum_of_divisors(k)
friendly_pairs = []

for i in range(2, k + 1):
    if i < divisor_sums[i] <= k and divisor_sums[divisor_sums[i]] == i:
        friendly_pairs.append((i, divisor_sums[i]))

for pair in friendly_pairs:
    print(pair[0], pair[1])

Этот код найдет все дружественные пары чисел, не превосходящие k, и выведет их в формате "число1 число2" по одной паре на строку.