Разбор номера 25 — ЕГЭ Информатика

📋 Условие

Задание 25 требует написать программу, которая находит делители числа, удовлетворяющие определённым условиям. Рассматриваем оптимальный алгоритм перебора.

🔍 Подробное решение

Задание 25 требует написать программу, которая находит делители числа, удовлетворяющие определённым условиям.

Типовые задачи 25:

1. Найти количество делителей числа
2. Найти сумму делителей
3. Найти делители, удовлетворяющие условию (чётные, нечётные, простые)
4. Найти число по его свойствам делителей

Шаблонный код:

```python
def divisors(n):
d = []
for i in range(1, int(n0.5) + 1):
if n % i == 0:
d.append(i)
if i != n // i:
d.append(n // i)
return sorted(d)

# Пример: найти количество делителей
def count_divisors(n):
cnt = 0
for i in range(1, int(n0.5) + 1):
if n % i == 0:
cnt += 2 if i != n // i else 1
return cnt
```

Задача на поиск числа по свойствам:
```python
for n in range(1, 100000):
d = divisors(n)
if len(d) == 16:
print(n, d)
```

Задача на сумму делителей:
```python
def sum_divisors(n):
s = 0
for i in range(1, int(n**0.5) + 1):
if n % i == 0:
s += i
if i != n // i:
s += n // i
return s
```

📚 Теория

Делители чисел. Проверка на простоту, поиск делителей по маске.

🐍 Шаблон Python

Python

# Простое число
def prost(n):
    return n > 1 and all(n%d != 0 for d in range(2, int(n**0.5)+1))

# Все делители
def delit(n):
    a = set()
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            a.add(i); a.add(n // i)
    return a

# Простые делители
def prost_del(n):
    a = set()
    for i in range(2, int(n**0.5)+1):
        if n % i == 0:
            if prost(i): a.add(i)
            if prost(n//i): a.add(n//i)
    return a

🐍 Альтернативный способ

Способ 2

# Маски fnmatch
from fnmatch import *
for i in range(18579, 10**10 + 1, 18579):
    if fnmatch(str(i), '54?1?3*7'):
        print(i, i // 18579)

# Пример: найти R с макс кол-вом делителей
mx = 0; ans = 0
for R in range(2, 10**6):
    d = len(delit(R))
    if d >= mx and prost(R + 2):
        mx = d; ans = R
print(ans)

# Поиск с условиями на делители
for n in range(2, 10**6):
    d = delit(n)
    pd = prost_del(n)
    if len(pd) == 3 and sum(d) % 2 == 0:
        print(n)

🔗 Полезные ссылки