Разбор 25 задания ЕГЭ по информатике (аналитическое + Python)

Как и раньше, считаем простые множители с повторениями.

 

Примеры:

 

16 = 2·2·2·2 → 4 множителя → подходит

 

24 = 2·2·2·3 → 4 множителя → подходит

 

60 = 2·2·3·5 → 4 множителя → подходит

 

30 = 2·3·5 → 3 множителя → не подходит

 

12 = 2·2·3 → 3 множителя → не подходит

 

 

---

Небольшое отступление:

Данный разбор больше подходит для тех, кто с математикой немного на "ты" .

Если вы пока не умеете возводить в степень в python или просто решать задачи быстрее 30 минут (одну задачу ЕГЭ), то готовьтесь в своем темпе, например дальше продолжая смотреть видео в интернете (разборы и так далее - название подготовки "Теоретик 1.0"), и вместо действия "делать вид" реально начните решать задачи. Быстрее, чем 30 минут на одну задачу. Это уже будет победа.

---

Продолжим.

0 и 1 не являются простыми числами.

Далее.

---

---

---

Все достаточно просто.

По этим шаблонам нам нужно построить все числа подходящие под условие задачи.

---

Полезный факт сразу:
самое маленькое число типа p·q·r·s – это 2·3·5·7 = 210 > 200,
значит тип 1+1+1+1 вообще не встретится в нашем диапазоне.

---

Делаем заготовку простых чисел.

Если честно, достаточно простых чисел до корень из 200, но опять же, не все знают почему... (попытаюсь всё объяснить ниже).

Давайте возьмем простых чисел с запасом.

2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47

---

Сначала будем проверять тип №1 (p⁴)

2·2·2·2 = 16 подходит (+1)

3·3·3·3 = 81 подходит (+1)

5·5·5·5 = 625 не подходит

---

Теперь проверим тип №2 (p³·q) p != q

Сначала подставим двойку вместо p

p = 2

Значит ищем произведение 2·2·2 = 8 (восьмерки) на простые числа.

8 · 3 = 24

8 · 5 = 40

8 · 7 = 56

8 · 11 = 88

8 · 13 = 104

8 · 17 = 136

8 · 19 = 152

8 · 23 = 184

дальше проверять двойку в кубе нет смыла. 29 при умножении на 8 точно больше 200.

---

Теперь подставим вместо p = 3

3 · 3 · 3 = 27

27 · 2 = 54

27 · 5 = 135

27 · 7 = 189

---

Если дойти до пятерки, то тут сразу не получится.

5 · 5 · 5 = 125

А 125 · 2 уже 250.

---

Теперь проверим тип №3 (p²·q²) p != q

2 · 2 · 3 · 3 = 36

2 · 2 · 5 · 5 = 100

2 · 2 · 7 · 7 = 196

---

Теперь проверим тип №3 (p²·q · r) p != q != r

сначала возьму p = 2

2 · 2 · q · r <= 200, значит q · r <= 50

4 · 3 · 5 = 60

4 · 3 · 7 = 84

4 · 3 · 11 = 132

4 · 3 · 13 = 156

4 · 5 · 7 = 140

---

Далее p = 3

3 · 3 · q · r <= 200, значит r · q <= 22

9 · 2 · 5 = 90

9 · 2 · 7 = 126

9 · 2 · 11 = 198

---

Все остальные варианты больше 200

---

И, наконец, проверим тип №4 (p · q · r · s) p != q != r != s

Было разобрано выше

2 · 3 · 5 · 7 > 200

---

Всего чисел 25 штук. (вроде посчитал).

---

Только вот тут у меня появились мысли, что на информатике бы обязательно использовать программы! Аналитическое решение хорошо, только до поры до времени (класса до 8 включительно) ( опять намек: начинаем уже серьезно готовиться, хватит заниматься ерундой).

---

Превратим наше аналитическое решение в программное.

План:

1) Найти все простые числа в нужном диапазоне (будем использовать решето Эратосфена)

2) Используя цикл while и способы из спортивного программирования будем проверять числа на соответствие условию.

В принципе весь план))

---

Отдельное отступление:

Для оптимизации на дистанции чисел 10 в 10 степени ниже дам рекомендации (после основного решения).

Python - не самый лучший инструмент для перебора большого количества чисел. 

Хотя библиотека sympy решила бы все наши проблемы, но пользоваться можно только базовой версией python. Устанавливать внешние библиотеки нельзя....

---

Пошаговое решение задачи в python

---

Выше обещал рассказать, почему же достаточно идти до корня из числа.

Не все поймут, но всё же)

Допустим, нам нужно найти делители числа 100.

Начнем с 1.

Но, будем записывать не только число, на которое при делении остаток 0, но и частное от деления.

Это увеличит эффективность программы в разы.

то есть, достаточно для числа 100 проверить всего лишь числа от 1 до 10.

100 % 1 == 0

Пишем в массив и 1 и 100

100 % 2 == 0

Пишем в массив и 2 и 50

100 % 4 == 0

Пишем в массив и 4 и 25.

И так далее.

Достаточно дойти до корня из 100 и будут найдены все делители.

---

Пример, который я расписывал даст понимание, что если у нас в задаче 10 в 10 степени, то обычными переборами можно сутки прождать. Но, для эффективности будем заранее искать делители только до корня из числа. Для 10 в 10 степени это всего лишь 100000.

---

Начнем с решета Эратосфена.

Это чтобы красиво записать название функции.

---

Решето Эратосфена создает список простых чисел.

Их мы и будем применять при поиске делителей.

---

Если что, это делители, которые могут быть до корня числа. То есть этим списком простых чисел мы проверим числа вплоть до 40000.

---

Решето Эратосфена вариант № 2

---

Все остальные варианты изменения программы будут лишь добавлять эстетику, но не скорость.

Первый вариант быстрее в перспективе, чем второй.

---

Теперь, когда мы знаем все простые числа, можно начать перебирать числа в диапазоне и выявлять те, которые образуются произведением 4 простых множителей.

Создадим функцию подсчёта количества простых делителей.

---

mx - переменная в которой буду хранить максимальный множитель. Ну, хитрю)), заранее делаю под основную задачу решение)

---

Остается перебрать по циклу for 

Пока делаем нашу задачу. С 2 до 200 все числа, которые образуются от произведения четырех простых множителей.

Всё четко, найдены наши 25 чисел.

---

Теперь немного подправим программу и найдем 5 значений по нашей основной задаче с сайта Полякова К.Ю.

---

Поправка

Случайно заметил, когда читал код.

Но, это не влияет на работу))

a[1] = 0

---

вот код для экспериментов.

import time

def sieve(n):
    a = [1] * (n + 1)
    ''' 0 и 1 не являются простыми числами '''
    a[0] = 0 
    a[1] = 0

    for p in range(2, int(n ** 0.5) + 1):
        if a[p] == 1:
            for m in range(p * p, n + 1, p):
                a[m] = 0

    b = []
    for i in range(2, n + 1):
        if a[i] == 1:
            b.append(i)

    return b

t1 = time.time()
b = sieve(int(29517513 ** 0.5) + 1)
t2 = time.time()
print('Простых чисел ', len(b), ' шт')
print('Время генерации ', t2 - t1, ' с')


def f(n):
    k = 0
    mx = 0
    x = n

    for p in b:
        if p * p > x:
            break

        while x % p == 0:
            x = x // p
            k = k + 1
            mx = p

    if x > 1:
        k = k + 1
        if x > mx:
            mx = x

    return k, mx

t3 = time.time()
c = 0
for i in range(24517513, 10 ** 10):
    k, mx = f(i)
    if k == 12:
        c = c + 1
        print(i, mx)
    if c == 5:
        break

t4 = time.time()
print('Время поиска ', t4 - t2, ' с')

---

Вывод по нашей задаче

---