Полный справочник функций для решения задач на делители
1. БАЗОВЫЕ ОПЕРАЦИИ С ЦИФРАМИ ЧИСЛА
Сумма цифр числа
def sum_of_digits(n):
"""Сумма цифр числа"""
n = abs(n)
result = 0
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 != 0
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):
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):
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):
candidate = n + 1
while not is_prime(candidate):
candidate += 1
return candidate
Найти предыдущее простое число перед n
def prev_prime(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):
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):
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):
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):
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):
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):
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):
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):
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):
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():
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():
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
2. Делители числа 18 – это 1 и 2, 3, 2·3=6, 3·3=9, 2·3
2=18.
Допустим, в разложение числа на простые множители входит ровно два простых нечётных числа каждое в первой степени: n = 2
kp
1p
2. Тогда число n делится на 1, p
1, p
2 и произведение p
1p
2 - всего 4 нечётных делителя. А нам нужно 5.
Попробуем взять одно из простых чисел во второй степени: n = 2
kp
12p
2. Тогда нечётными делителями числа n будут: 1, p
1, p
2, p
12, p
1p
2, p
12p
2. Всего 6 делителей (больше чем нам нужно). Очевидно, что при увеличении количества нечётных простых делителей мы также получим больше 5 нечётных делителей исходного числа.
Вывод: если число имеет ровно 5 нечётных делителей, в его разложение на простые множители может входить только
одно нечётное простое число. Тогда этими делителями будут 1, p, p
2, p
3, p
4, а само число имеет вид n = 2
kp
4, где k – натуральное число или ноль, p – нечётное простое число.
Алгоритм
- Перебрать все числа из заданного отрезка.
- Убрать из разложения все множители вида (2k) - пока число четное, будем уменьшать его в 2 раза.
- Найти, корень четвертой степени из оставшегося числа.
- Если оставшееся число является четвертой степенью простого числа, то найдено искомое число.
- Для определения наименьшего нечётного делителя, отличного от единицы, используем это найденное простое число.
Примечание: Все функции работают в разумное время для чисел до 10^9.