1) Выведите все простые натуральные делители заданного натурального числа N, учитывая их кратность. Необходимо

1) Для решения данной задачи, мы можем использовать алгоритм поиска простых чисел - Решето Эратосфена, который позволяет нам найти все простые числа до заданного числа N.

Создадим массив isPrime размером N+1, в котором будем хранить информацию о том, является ли число простым или нет. Изначально, все элементы массива проставим 1, что означает, что все числа считаются простыми.

Затем, начиная с числа 2, будем перебирать все числа до \(\sqrt{N}\). Если текущее число i является простым (isPrime[i] = 1), то помечаем все числа, кратные i, как составные (isPrime[j] = 0), начиная с числа i^2 и увеличивая индекс j на i в каждой итерации.

После обработки всех чисел, в массиве isPrime будут сохранены все простые числа до N. Пройдем по массиву и выведем все простые делители числа N, учитывая их кратность.

Вот пошаговое решение:

1. Создадим массив isPrime размером N+1 и проинициализируем его значениями 1.
2. Установим переменную sqrtN равной \(\sqrt{N}\).
3. Начинаем цикл от числа 2 до sqrtN:
- Если isPrime[i] равно 1:
- Начинаем вложенный цикл от числа i^2 до N с шагом i:
- Помечаем isPrime[j] как 0.
4. Пройдем по массиву isPrime:
- Если i является делителем числа N, выведем i.

Ниже приведена реализация алгоритма на языке Python:

python

import math



def find_prime_divisors(N):

    isPrime = [1] * (N + 1)

    sqrtN = int(math.sqrt(N))

    for i in range(2, sqrtN + 1):

        if isPrime[i] == 1:

            for j in range(i * i, N + 1, i):

                isPrime[j] = 0

    prime_divisors = []

    for i in range(2, N + 1):

        if isPrime[i] == 1 and N % i == 0:

            prime_divisors.append(i)

    return prime_divisors



N = int(input("Введите натуральное число N: "))

prime_divisors = find_prime_divisors(N)

print("Простые делители числа", N, ":")

for divisor in prime_divisors:

    print(divisor)

2) Для нахождения значения τ(n) (количества натуральных делителей числа n) и σ(n) (суммы всех натуральных делителей числа n), мы также можем использовать алгоритм на основе разложения числа на простые множители.

После нахождения простых делителей числа n с помощью описанного выше алгоритма, мы можем выразить n в виде произведения простых чисел: \(n = \prod_{i=1}^{k} p_i^{a_i}\), где \(p_i\) - простые делители, а \(a_i\) - их кратности.

Тогда значение τ(n) можно выразить как произведение \((a_1 + 1)(a_2 + 1)...(a_k + 1)\), а значение σ(n) - как \((p_1^{0} + p_1^{1} + ... + p_1^{a_1})(p_2^{0} + p_2^{1} + ... + p_2^{a_2})...(p_k^{0} + p_k^{1} + ... + p_k^{a_k})\).

Вот пошаговое решение для нахождения τ(n) и σ(n):

1. Найдем простые делители числа n с помощью алгоритма из предыдущего решения.
2. Создадим переменные τ и σ и установим их значения равными 1.
3. Пройдем по каждому простому делителю p и его кратности a:
- Увеличим τ на (a + 1).
- Увеличим σ на \((p^{0} + p^{1} + ... + p^{a})\).
4. Выведем значения τ и σ.

Ниже приведена реализация алгоритма на языке Python:

python

def find_divisors_count_and_sum(N):

    prime_divisors = find_prime_divisors(N)

    divisors_count = 1

    divisors_sum = 1

    for divisor in prime_divisors:

        power = 0

        while N % divisor == 0:

            power += 1

            N //= divisor

        divisors_count *= (power + 1)

        divisors_sum *= (pow(divisor, power + 1) - 1) // (divisor - 1)

    return divisors_count, divisors_sum



n = int(input("Введите натуральное число n: "))

divisors_count, divisors_sum = find_divisors_count_and_sum(n)

print("Значение τ(n):", divisors_count)

print("Значение σ(n):", divisors_sum)

3) Чтобы найти все дружественные числа n, мы можем пройтись по всем натуральным числам до заданного предела и проверить, являются ли они дружественными парами.

Для каждого числа n в диапазоне, найдем сумму его делителей (используя алгоритм из предыдущего решения) и проверим, равна ли эта сумма другому числу m. Если суммы делителей равны друг другу, и n ≠ m, то числа n и m являются дружественными парами.

Вот пошаговое решение:

1. Создадим пустой список friendly_numbers.
2. Пройдем по каждому числу n от 1 до заданного предела (например, 10^6):
- Найдем сумму делителей числа n с помощью алгоритма из предыдущего решения.
- Проверим, существует ли в friendly_numbers число, равное сумме делителей n:
- Если есть, продолжим цикл, так как числа уже дружественные.
- Найдем сумму делителей найденной суммы делителей n и сравним ее с числом n:
- Если суммы равны и n ≠ найденной суммы делителей, то добавим числа n и найденную сумму делителей в список friendly_numbers.
3. Выведем все числа из списка friendly_numbers.

Ниже приведена реализация алгоритма на языке Python:

python

def find_friendly_numbers(limit):

    friendly_numbers = []

    for n in range(1, limit + 1):

        divisors_sum_n = find_divisors_count_and_sum(n)[1]

        if divisors_sum_n in friendly_numbers:

            continue

        divisors_sum_m = find_divisors_count_and_sum(divisors_sum_n)[1]

        if divisors_sum_m == n and n != divisors_sum_n:

            friendly_numbers.append(n)

            friendly_numbers.append(divisors_sum_n)

    return friendly_numbers



limit = int(input("Введите предел для поиска дружественных чисел: "))

friendly_numbers = find_friendly_numbers(limit)

print("Дружественные числа:")

for number in friendly_numbers:

    print(number)

Обратите внимание, что для больших значений предела задачи могут потребоваться значительные ресурсы и время для выполнения. Рекомендуется выбирать предел, который не превышает 10^6 для оптимальной производительности.