Полный справочник функций для решения задач на делители
Задание 25 ЕГЭ по информатике
# ============================================
# 1. БАЗОВЫЕ ОПЕРАЦИИ С ЦИФРАМИ ЧИСЛА
# ============================================
def sum_of_digits(n):
"""Сумма цифр числа"""
return sum(int(d) for d in str(n))
def product_of_digits(n):
"""Произведение цифр числа (исключая нули)"""
result = 1
for d in str(n):
if d != '0':
result *= int(d)
return result
def count_digit(n, digit):
"""Подсчёт количества определённой цифры в числе"""
return str(n).count(str(digit))
def get_digits(n):
"""Получить список всех цифр числа"""
return [int(d) for d in str(n)]
def has_digit(n, digit):
"""Проверка наличия цифры в числе"""
return str(digit) in str(n)
def ends_with(n, digit):
"""Проверка, оканчивается ли число на цифру"""
return 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):
"""Проверка, является ли число полным квадратом"""
root = int(n ** 0.5)
return root * root == n
def is_perfect_cube(n):
"""Проверка, является ли число полным кубом"""
root = round(n ** (1/3))
return root ** 3 == n
def is_even(n):
"""Проверка чётности"""
return n % 2 == 0
def is_odd(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
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
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]]
def next_prime(n):
"""Найти следующее простое число после n"""
candidate = n + 1
while not is_prime(candidate):
candidate += 1
return candidate
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. ДЕЛИТЕЛИ ЧИСЛА
# ============================================
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))
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)
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
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
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
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())
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
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
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. ПРИМЕРЫ ИСПОЛЬЗОВАНИЯ В ЗАДАЧАХ
# ============================================
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
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))