ЕГЭ. Вопрос 25. Полный справочник функций для решения задач на делители

Полный справочник функций для решения задач на делители

---

1. БАЗОВЫЕ ОПЕРАЦИИ С ЦИФРАМИ ЧИСЛА

Сумма цифр числа

def sum_of_digits(n):
    """Сумма цифр числа"""
    n = abs(n)
    result = 1
    while n != 0:
        result += n % 10
    return result
    

Произведение цифр числа (исключая нули)

def product_of_digits(n):
    """Произведение цифр числа (исключая нули)"""
    n = abs(n)
    result = 1
    while n != 0:
        if n % 10 != 0:
            result *= n % 10
    return result
    

Подсчёт количества определённой цифры в числе

def count_digit(n, digit):
    """Подсчёт количества определённой цифры в числе"""
    n = abs(n)
    result = 0
    while n != 0:
        if n % 10 == digit:
            result += 1
        n = n // 10
    return result
    

Получить список всех цифр числа

def get_digits(n):
    n = abs(n)
    """Получить список всех цифр числа"""
    result = []
    while n != 0:
        result += [n % 10]
        n = n // 10
    return result
    

Проверка наличия цифры в числе

def has_digit(n, digit):
    """Проверка наличия цифры в числе"""
    n = abs(n)
    while n != 0:
        if n % 10 == digit:
            return True
        n = n // 10
    return False
    

Проверка, оканчивается ли число на цифру

def ends_with(n, digit):
    """Проверка, оканчивается ли число на цифру"""
    return abs(n) % 10 == digit
    

Проверка, начинается ли число с цифры

def starts_with(n, digit):
    """Проверка, начинается ли число с цифры"""
    return str(n)[0] == str(digit)
    

---

2. ПРОВЕРКА СВОЙСТВ ЧИСЛА

Проверка, является ли число палиндромом

def is_palindrome(n):
    """Проверка, является ли число палиндромом"""
    s = str(n)
    return s == s[::-1]
    

Проверка, является ли число полным квадратом

def is_perfect_square(n):
    n = abs(n)
    """Проверка, является ли число полным квадратом"""
    root = int(n ** 0.5)
    return root * root == n
    

Проверка, является ли число полным кубом

def is_perfect_cube(n):
     n = abs(n)
    """Проверка, является ли число полным кубом"""
    root = round(n ** (1/3))
    return root ** 3 == n
    

Проверка чётности

def is_even(n):
    n = abs(n)
    """Проверка чётности"""
    return n % 2 == 0
    

Проверка нечётности

def is_odd(n):
    n = abs(n)
    """Проверка нечётности"""
    return n % 2 == 1
    

---

3. ПРОСТЫЕ ЧИСЛА

Проверка, является ли число простым

def is_prime(n):
    """Проверка, является ли число простым"""
    if n < 2:
        return False
    if n == 2:
        return True
    if n % 2 == 0:
        return False
    for i in range(3, int(n**0.5) + 1, 2):
        if n % i == 0:
            return False
    return True
    

Оптимизированная проверка простоты (пропуск кратных 2 и 3)

def is_prime_optimized(n):
    """Оптимизированная проверка простоты (пропуск кратных 2 и 3)"""
    if n <= 1:
        return False
    if n <= 3:
        return True
    if n % 2 == 0 or n % 3 == 0:
        return False
    i = 5
    while i * i <= n:
        if n % i == 0 or n % (i + 2) == 0:
            return False
        i += 6
    return True
    

Решето Эратосфена - генерация всех простых чисел до limit

def sieve_of_eratosthenes(limit):
    """Решето Эратосфена - генерация всех простых чисел до limit"""
    is_prime = [True] * (limit + 1)
    is_prime[0] = is_prime[1] = False
    
    for i in range(2, int(limit**0.5) + 1):
        if is_prime[i]:
            for j in range(i*i, limit + 1, i):
                is_prime[j] = False
    
    return [i for i in range(2, limit + 1) if is_prime[i]]
    

Найти следующее простое число после n

def next_prime(n):
    """Найти следующее простое число после n"""
    candidate = n + 1
    while not is_prime(candidate):
        candidate += 1
    return candidate
    

Найти предыдущее простое число перед n

def prev_prime(n):
    """Найти предыдущее простое число перед n"""
    if n <= 2:
        return None
    candidate = n - 1
    while candidate >= 2 and not is_prime(candidate):
        candidate -= 1
    return candidate if candidate >= 2 else None
    

---

4. ДЕЛИТЕЛИ ЧИСЛА

Найти все делители числа (включая 1 и само число)

def find_divisors(n):
    """Найти все делители числа (включая 1 и само число)"""
    divisors = set()
    for i in range(1, int(n**0.5) + 1):
        if n % i == 0:
            divisors.add(i)
            divisors.add(n // i)
    return sorted(list(divisors))
    

Найти собственные делители (без 1 и самого числа)

def find_proper_divisors(n):
    """Найти собственные делители (без 1 и самого числа)"""
    divisors = find_divisors(n)
    if len(divisors) > 2:
        return divisors[1:-1]
    return []
    

Подсчёт количества делителей

def count_divisors(n):
    """Подсчёт количества делителей"""
    count = 0
    for i in range(1, int(n**0.5) + 1):
        if n % i == 0:
            count += 1 if i * i == n else 2
    return count
    

Сумма всех делителей числа

def sum_divisors(n):
    """Сумма всех делителей числа"""
    total = 0
    for i in range(1, int(n**0.5) + 1):
        if n % i == 0:
            total += i
            if i != n // i:
                total += n // i
    return total
    

Сумма собственных делителей (без самого числа)

def sum_proper_divisors(n):
    """Сумма собственных делителей (без самого числа)"""
    return sum_divisors(n) - n
    

Произведение всех делителей числа

def product_divisors(n):
    """Произведение всех делителей числа"""
    divisors = find_divisors(n)
    result = 1
    for d in divisors:
        result *= d
    return result
    

Найти делители, удовлетворяющие условию

def find_divisors_with_condition(n, condition_func):
    """Найти делители, удовлетворяющие условию"""
    divisors = []
    for i in range(1, int(n**0.5) + 1):
        if n % i == 0:
            if condition_func(i):
                divisors.append(i)
            if i != n // i and condition_func(n // i):
                divisors.append(n // i)
    return sorted(divisors)
    

Минимальный делитель, кроме 1

def min_divisor_except_one(n):
    """Минимальный делитель, кроме 1"""
    for i in range(2, int(n**0.5) + 1):
        if n % i == 0:
            return i
    return n  # Число простое
    

Максимальный делитель, кроме самого числа

def max_divisor_except_self(n):
    """Максимальный делитель, кроме самого числа"""
    for i in range(2, int(n**0.5) + 1):
        if n % i == 0:
            return n // i
    return 1  # Число простое
    

---

5. ПРОСТЫЕ ДЕЛИТЕЛИ И ФАКТОРИЗАЦИЯ

Разложение на простые множители (список)

def prime_factorization(n):
    """Разложение на простые множители (список)"""
    factors = []
    d = 2
    while d * d <= n:
        while n % d == 0:
            factors.append(d)
            n //= d
        d += 1
    if n > 1:
        factors.append(n)
    return factors
    

Разложение на простые множители (словарь: простое → степень)

def prime_factorization_dict(n):
    """Разложение на простые множители (словарь: простое -> степень)"""
    factors = {}
    d = 2
    while d * d <= n:
        while n % d == 0:
            factors[d] = factors.get(d, 0) + 1
            n //= d
        d += 1
    if n > 1:
        factors[n] = factors.get(n, 0) + 1
    return factors
    

Список уникальных простых делителей

def unique_prime_factors(n):
    """Список уникальных простых делителей"""
    return list(prime_factorization_dict(n).keys())
    

Количество простых делителей

def count_prime_factors(n, count_duplicates=True):
    """Количество простых делителей"""
    if count_duplicates:
        return len(prime_factorization(n))
    else:
        return len(unique_prime_factors(n))
    

Сумма простых делителей

def sum_prime_factors(n, unique_only=False):
    """Сумма простых делителей"""
    if unique_only:
        return sum(unique_prime_factors(n))
    else:
        return sum(prime_factorization(n))
    

Произведение простых делителей

def product_prime_factors(n, unique_only=True):
    """Произведение простых делителей"""
    if unique_only:
        result = 1
        for p in unique_prime_factors(n):
            result *= p
        return result
    else:
        return n  # Произведение всех простых множителей = само число
    

Наибольший простой делитель

def largest_prime_factor(n):
    """Наибольший простой делитель"""
    factor = None
    d = 2
    while d * d <= n:
        while n % d == 0:
            factor = d
            n //= d
        d += 1
    if n > 1:
        factor = n
    return factor
    

Наименьший простой делитель

def smallest_prime_factor(n):
    """Наименьший простой делитель"""
    if n <= 1:
        return None
    for i in range(2, int(n**0.5) + 1):
        if n % i == 0:
            return i
    return n
    

---

6. СПЕЦИАЛЬНЫЕ ФУНКЦИИ ДЛЯ ДЕЛИТЕЛЕЙ

Найти все нечётные делители

def find_odd_divisors(n):
    """Найти все нечётные делители"""
    return find_divisors_with_condition(n, is_odd)
    

Найти все чётные делители

def find_even_divisors(n):
    """Найти все чётные делители"""
    return find_divisors_with_condition(n, is_even)
    

Найти все простые делители (включая повторения)

def find_prime_divisors(n):
    """Найти все простые делители (включая повторения)"""
    return [d for d in find_divisors(n) if is_prime(d)]
    

Два наибольших делителя, кроме самого числа

def two_largest_divisors(n):
    """Два наибольших делителя, кроме самого числа"""
    divisors = find_divisors(n)[:-1]  # Исключаем само число
    if len(divisors) >= 2:
        return divisors[-2], divisors[-1]
    elif len(divisors) == 1:
        return None, divisors[0]
    else:
        return None, None
    

Два наименьших делителя, кроме 1

def two_smallest_divisors(n):
    """Два наименьших делителя, кроме 1"""
    divisors = find_divisors(n)[1:]  # Исключаем 1
    if len(divisors) >= 2:
        return divisors[0], divisors[1]
    elif len(divisors) == 1:
        return divisors[0], None
    else:
        return None, None
    

M(N) - сумма мин и макс делителей, кроме 1 и N

def M_function(n):
    """M(N) - сумма мин и макс делителей, кроме 1 и N"""
    divisors = find_proper_divisors(n)
    if len(divisors) >= 2:
        return divisors[0] + divisors[-1]
    elif len(divisors) == 1:
        return divisors[0]
    else:
        return 0
    

K(N) - сумма k наибольших делителей, кроме N

def K_function(n, k=2):
    """K(N) - сумма k наибольших делителей, кроме N"""
    divisors = find_divisors(n)[:-1]  # Исключаем само число
    if len(divisors) >= k:
        return sum(divisors[-k:])
    else:
        return 0
    

---

7. ПРОВЕРКИ НА ОСОБЫЕ ТИПЫ ЧИСЕЛ

Проверка совершенного числа (равно сумме своих делителей, кроме себя)

def is_perfect_number(n):
    """Проверка совершенного числа (равно сумме своих делителей, кроме себя)"""
    return sum_proper_divisors(n) == n
    

Проверка избыточного числа (сумма делителей больше самого числа)

def is_abundant_number(n):
    """Проверка избыточного числа (сумма делителей больше самого числа)"""
    return sum_proper_divisors(n) > n
    

Проверка недостаточного числа (сумма делителей меньше самого числа)

def is_deficient_number(n):
    """Проверка недостаточного числа (сумма делителей меньше самого числа)"""
    return sum_proper_divisors(n) < n
    

Проверка полупростого числа (произведение ровно двух простых)

def is_semiprime(n):
    """Проверка полупростого числа (произведение ровно двух простых)"""
    factors = prime_factorization(n)
    return len(factors) == 2
    

Проверка бесквадратного числа (не делится на квадрат простого)

def is_squarefree(n):
    """Проверка бесквадратного числа (не делится на квадрат простого)"""
    factors = prime_factorization_dict(n)
    return all(power == 1 for power in factors.values())
    

Проверка мощного числа (все простые делители в степени >= 2)

def is_powerful_number(n):
    """Проверка мощного числа (все простые делители в степени >= 2)"""
    if n == 1:
        return True
    factors = prime_factorization_dict(n)
    return all(power >= 2 for power in factors.values())
    

---

8. ВСПОМОГАТЕЛЬНЫЕ ФУНКЦИИ

НОД двух чисел (алгоритм Евклида)

def gcd(a, b):
    """НОД двух чисел (алгоритм Евклида)"""
    while b:
        a, b = b, a % b
    return a
    

НОК двух чисел

def lcm(a, b):
    """НОК двух чисел"""
    return abs(a * b) // gcd(a, b)
    

Проверка взаимной простоты

def are_coprime(a, b):
    """Проверка взаимной простоты"""
    return gcd(a, b) == 1
    

Функция Эйлера - количество чисел, взаимно простых с n

def euler_totient(n):
    """Функция Эйлера - количество чисел, взаимно простых с n"""
    result = n
    p = 2
    while p * p <= n:
        if n % p == 0:
            while n % p == 0:
                n //= p
            result -= result // p
        p += 1
    if n > 1:
        result -= result // n
    return result
    

Обобщённая функция делителей σ_k(n) = сумма k-х степеней делителей

def divisor_function(n, k=1):
    """Обобщённая функция делителей σ_k(n) = сумма k-х степеней делителей"""
    total = 0
    for i in range(1, int(n**0.5) + 1):
        if n % i == 0:
            total += i**k
            if i != n // i:
                total += (n // i)**k
    return total
    

---

9. ОПТИМИЗИРОВАННЫЕ ФУНКЦИИ ДЛЯ БОЛЬШИХ ЧИСЕЛ

Тест Миллера-Рабина на простоту (вероятностный)

def is_prime_miller_rabin(n, k=5):
    """Тест Миллера-Рабина на простоту (вероятностный)"""
    import random
    
    if n < 2:
        return False
    if n == 2 or n == 3:
        return True
    if n % 2 == 0:
        return False
    
    # Представляем n-1 как 2^r * d
    r, d = 0, n - 1
    while d % 2 == 0:
        r += 1
        d //= 2
    
    # Проверяем k раз
    for _ in range(k):
        a = random.randrange(2, n - 1)
        x = pow(a, d, n)
        
        if x == 1 or x == n - 1:
            continue
        
        for _ in range(r - 1):
            x = pow(x, 2, n)
            if x == n - 1:
                break
        else:
            return False
    
    return True
    

Ро-алгоритм Полларда для факторизации

def pollard_rho(n):
    """Ро-алгоритм Полларда для факторизации"""
    if n % 2 == 0:
        return 2
    
    x = 2
    y = 2
    d = 1
    
    f = lambda x: (x * x + 1) % n
    
    while d == 1:
        x = f(x)
        y = f(f(y))
        d = gcd(abs(x - y), n)
    
    return d if d != n else None
    

---

10. ПРИМЕРЫ ИСПОЛЬЗОВАНИЯ В ЗАДАЧАХ

Пример: найти числа > 1000000, где сумма делителей оканчивается на 6

def example_task_1():
    """Пример: найти числа > 1000000, где сумма делителей оканчивается на 6"""
    count = 0
    n = 1000001
    while count < 5:
        if sum_divisors(n) % 10 == 6:
            print(n, sum_divisors(n))
            count += 1
        n += 1
    

Пример: числа, являющиеся произведением двух простых

def example_task_2():
    """Пример: числа, являющиеся произведением двух простых"""
    def check_two_primes(n):
        factors = prime_factorization(n)
        return len(factors) == 2
    
    count = 0
    n = 100
    while count < 5:
        if check_two_primes(n):
            factors = prime_factorization(n)
            print(n, factors[0], factors[1])
            count += 1
        n += 1
    

Пример: делители, оканчивающиеся на 7

def example_task_3():
    """Пример: делители, оканчивающиеся на 7"""
    n = 1125000
    divisors_ending_7 = find_divisors_with_condition(
        n, 
        lambda x: x % 10 == 7 and x != 7 and x != n
    )
    if divisors_ending_7:
        print(n, min(divisors_ending_7))

Когда перебор не помогает

Найдите все натуральные числа, принадлежащие отрезку [77777777; 88888888], у которых ровно пять различных нечётных делителей (количество чётных делителей может быть любым).
В ответе перечислите найденные числа, справа от каждого числа запишите его наименьший нечётный делитель, не равный 1.

Решение

Простой перебор всех чисел и подсчет числа делителей будет занимать некоторое время (порядка 20 минут). Поэтому, воспользуемся знаниями из области математики.
 
Любое натуральное число можно представить в виде произведения простых множителей: 
n = p1k1p2k2...pmkm.
Здесь pi (i=1, ...m) – различные простые делители, а ki (i=1, ..., m) – их кратности (натуральные числа).
 
Каждый делитель числа представляется как произведение некоторых или всех простых множителей числа в различных степенях Поэтому, все делители числа (кроме 1) можно получить, взяв произведения всевозможных комбинаций простых множителей. Например, 18 = 2·3². Делители числа 18 – это 1 и 2, 3, 2·3=6, 3·3=9, 2·3²=18.

Допустим, в разложение числа на простые множители входит ровно два простых нечётных числа каждое в первой степени: n = 2^kp₁p₂. Тогда число n делится на 1, p₁, p₂ и произведение p₁p₂ - всего 4 нечётных делителя. А нам нужно 5. 

Попробуем взять одно из простых чисел во второй степени:  n = 2^kp₁²p₂. Тогда нечётными делителями числа n будут: 1, p₁, p₂, p₁², p₁p₂, p₁²p₂. Всего 6 делителей (больше чем нам нужно). Очевидно, что при увеличении количества нечётных простых делителей мы также получим больше 5 нечётных делителей исходного числа.

Вывод: если число имеет ровно 5 нечётных делителей, в его разложение на простые множители может входить только одно нечётное простое число. Тогда этими делителями будут 1, p, p², p³, p⁴, а само число имеет вид n = 2^kp⁴, где k – натуральное число или ноль, p – нечётное простое число.
 

Алгоритм

1. Перебрать все числа из заданного отрезка.
2. Убрать из разложения все множители вида (2^k) - пока число четное, будем уменьшать его в 2 раза.
3. Найти, корень четвертой степени из оставшегося числа.
4. Если оставшееся число является четвертой степенью простого числа, то найдено искомое число.
5. Для определения наименьшего нечётного делителя, отличного от единицы, используем это найденное простое число.

---

Примечание: Все функции работают в разумное время для чисел до 10^9.