Занятие 3.5 Алгоритмы для работы с числами (25)

1. Алгоритмы для работы с числами

2. Суть задания 25

• Это задача на обработку целых чисел. Нужно написать
код, который найдет все числа, подходящие под
определенное условие.
• Два основных типа :
• 1. Маски чисел
• 2. Поиск делителей (классический формат)

3. Маски чисел

Нужно найти числа, которые делятся на заданное
число (например, на 2024) и соответствуют маске. В
маске символ ? означает ровно одну любую цифру, а
* - любую последовательность цифр (в том числе
пустую).

4. Маски чисел (?)

? может быть любой цифрой от 0 до 9
2141013
2141113
2141213
2141313
2141?13
2141413
2141513
2141613
2141713
2141813
2141913

5. Маски чисел (*)

* может быть последовательностью цифр от 0 до 9
214113
2141013
2141113
…
2141*13
2141813
2141913
21410013
21410113
…
21419813
21419913
И так далее …

6. Маски чисел (? и *)

? – пустой слот, который обязан быть чем-то заполнен
* – как «пружина», которая может быть полностью сжата (пустая), или
разжата на определённое расстояние (последовательность определённой
длины)
5
1
19 4
2 3 78
05
2 ? 4
*
7
может тянуться
бесконечно
пусто
4
1 1
1 2 5

7. Маски чисел (пример)

• Среди натуральных чисел, не превышающих 10^9,
найдите все числа, соответствующие маске
12345?7?8, делящиеся на число 23 без остатка.
• В ответе запишите в первом столбце таблицы все
найденные числа в порядке возрастания, а во
втором столбце — соответствующие им результаты
деления этих чисел на 23.
• Количество строк в таблице для ответа избыточно.

8. Маски чисел (пример)

• 12345 x 7 y 8
• Сколько тут комбинаций?
x = 0: 12345 [0] 7 [0] 8
...
12345 [0] 7 [1] 8
...
12345 [0] 7 [2] 8
…
x = 1: 12345 [1] 7 [0] 8
...
12345 [1] 7 [1] 8

9. Решение

for x in range(10):
for y in range(10):
s = f"12345{x}7{y}8"
n = int(s)
if n % 23 == 0:
print(n, n // 23)
# 123450798 5367426
# 123451718 5367466
# 123453788 5367556
# 123454708 5367596
# 123456778 5367686
# 123459768 5367816

10. Задача 1

• Маска числа — это последовательность цифр, в
которой могут встречаться специальные символы
«?» и «*». Символ «?» означает ровно одну
произвольную цифру, символ «*» означает
произвольную (в том числе пустую)
последовательность цифр.
• Пример. Маске 123*4?5 соответствуют числа
123405 и 12376415.
• Найдите все натуральные числа, не
превышающие 10^9, которые соответствуют маске
12*63?5? и при этом без остатка делятся на
3123.В ответе запишите все найденные числа в
порядке возрастания.

11. Задача 1

• Как определить, до какого момента будем
«растягивать» * ?
• 10^9 =1000000000 - лимит
1263?5?
12063?5?
120063?5?
1200063?5? – Превышает лимит!
• Если * является последовательностью из 3 и
более цифр, наше число не подойдёт под
условие, следовательно, остаётся 3 варианта, 0, 1
или 2 цифры в *

12. Решение

13. Библиотека fnmatch

• Встроенная библиотека fnmatch в Python
предназначена для проверки соответствия
текстовых строк заданному шаблону (маске). Она
использует простые символы подстановки, где ?
заменяет ровно один любой символ, а * — любую (в
том числе пустую) последовательность символов.
Синтаксис масок в библиотеке полностью совпадает
с правилами из условий экзаменационных задач.
• import fnmatch
• if fnmatch.fnmatch(str(n), '12345?7?8’):
# n подходит под маску

14. Решение задачи 1

• import fnmatch
• for n in range(0, 10**9, 3123):
if fnmatch.fnmatch(str(n), ' 12*63?5?'):
print(n)

15. Задача 1

• 12363957
• 120663351
• 120963159
• 124763850
• 125063658

16. Задача 2

• Маска числа — это последовательность цифр, в
которой могут встречаться специальные символы
«?» и «*». Символ «?» означает ровно одну
произвольную цифру, символ «*» означает
произвольную (в том числе пустую)
последовательность цифр.
• Пример. Маске 123*4?5 соответствуют числа
123 405 и 12 376 415.
• Найдите все натуральные числа, не
превышающие 10^10, которые соответствуют
маске 1?493*41 и при этом без остатка делятся на
2023. В ответе запишите все найденные числа в
порядке возрастания.

17. Задача 2

• 1349341
• 1249338041
• 1549348941
• 1849359841

18. Задача 3

• Назовём маской числа последовательность цифр, в
которой также могут встречаться следующие символы:—
символ «?» означает ровно одну произвольную
цифру;— символ «*» означает любую
последовательность цифр произвольной длины; в том
числе «*» может задавать и пустую последовательность.
• Например, маске 123*4?5 соответствуют числа 123405 и
12300405.Среди натуральных чисел, не превышающих
108, найдите все числа, соответствующие маске
12??36*1, делящиеся на 273 без остатка.
• В ответе запишите в первом столбце таблицы все
найденные числа в порядке возрастания, а во втором
столбце — соответствующие им результаты деления
этих чисел на 273.
• Количество строк в таблице для ответа избыточно.

19. Задача 3

• 1271361 4657
• 12633621 46277
• 12663651 46387
• 12693681 46497

20. Задача 4

• Маска числа — это последовательность цифр, в
которой могут встречаться специальные символы
«?» и «*». Символ «?» означает ровно одну
произвольную цифру, символ «*» означает
произвольную (в том числе пустую)
последовательность цифр.
• Пример. Маске 123*4?5 соответствуют числа 123405
и 12376415.
• Найдите все натуральные числа, не превышающие
10^10, которые соответствуют маске 1?7246*1 и при
этом без остатка делятся на 4173.
• В ответе запишите все найденные числа в порядке
возрастания.

21. Задача 4

• 1072461
• 1272460371
• 1772469231

22. Задача 5

• Назовём маской числа последовательность цифр, в
которой также могут встречаться следующие символы:—
символ «?» означает ровно одну произвольную
цифру;— символ «*» означает любую
последовательность цифр произвольной длины; в том
числе «*» может задавать и пустую последовательность.
• Например, маске 123*4?5 соответствуют числа 123405 и
12300405.Среди натуральных чисел, не превышающих
108, найдите все числа, соответствующие маске
12??1*56, делящиеся на 317 без остатка.
• В ответе запишите в первом столбце таблицы все
найденные числа в порядке возрастания, а во втором
столбце — соответствующие им результаты деления
этих чисел на 317.
• Количество строк в таблице для ответа избыточно.

23. Задача 5

• 1226156 3868
• 12321156 38868
• 12511356 39468
• 12701556 40068
• 12891756 40668

24. Задача 6

• Маска числа — это последовательность цифр, в
которой могут встречаться специальные символы
«?» и «*». Символ «?» означает ровно одну
произвольную цифру, символ «*» означает
произвольную (в том числе пустую)
последовательность цифр.
• Пример. Маске 123*4?5 соответствуют числа 123405
и 12376415.
• Найдите все натуральные числа, не превышающие
10^10, которые соответствуют маске 1?7602*0 и при
этом без остатка делятся на 4891. В ответе
запишите все найденные числа в порядке
возрастания.

25. Задача 6

• 1076020
• 10760200
• 107602000
• 1076020000
• 1576026930

26. Задача 7

• Назовём маской числа последовательность цифр, в
которой также могут встречаться следующие символы:—
символ «?» означает ровно одну произвольную
цифру;— символ «*» означает любую
последовательность — цифр произвольной длины; в том
числе «*» может задавать и пустую последовательность.
• Например, маске 123*4?5 соответствуют числа 123405 и
12300405.
• Среди натуральных чисел, не превышающих 10^8,
найдите все числа, соответствующие маске 3?1*57,
делящиеся на 2023 без остатка.
• В ответе запишите в первом столбце таблицы все
найденные числа в порядке возрастания, а во втором
столбце — соответствующие им результаты деления
этих чисел на 2023.Количество строк в таблице для
ответа избыточно.

27. Задача 7

• 321657 159
• 34105757 16859
• 35117257 17359
• 36128757 17859
• 37140257 18359
• 38151757 18859
• 39163257 19359

28. Задача 8

• Назовём маской числа последовательность цифр, в
которой также могут встречаться следующие символы:—
символ «?» означает ровно одну произвольную
цифру;— символ «*» означает любую
последовательность цифр произвольной длины; в том
числе «*» может задавать и пустую последовательность.
• Например, маске 123*4?5 соответствуют числа 123405 и
12300405.
• Среди натуральных чисел, не превышающих 1010,
найдите все числа, соответствующие маске 3?12?14*5,
делящиеся на 1917 без остатка. В ответе запишите в
первом столбце таблицы все найденные числа в порядке
возрастания, а во втором столбце — соответствующие
им результаты деления этих чисел на 1917.
• Количество строк в таблице для ответа избыточно.

29. Задача 8

• 351261495 183235
• 3212614035 1675855
• 3412614645 1780185
• 3712414275 1936575
• 3912414885 2040905

30. Задача 9

• Назовём маской числа последовательность цифр, в
которой также могут встречаться следующие
символы:— символ «?» означает ровно одну
произвольную чётную цифру;— символ «*» означает
любую последовательность цифр произвольной
длины; в том числе «*» может задавать и пустую
последовательность.
• Например, маске 123*4?5 соответствуют
числа 123 405 и 12 300 405.Среди натуральных
чисел, не превышающих 10^10, найдите все числа,
соответствующие маске 7?23?64*8, делящиеся
на 2026 без остатка.
• В ответе запишите все найденные числа в порядке
возрастания.

31. Задача 9

• 782386498
• 7023064168
• 7023864438
• 7623064068
• 7623864338

32. Задача 10

• Назовём маской числа последовательность цифр, в
которой также могут встречаться следующие
символы:— символ «?» означает ровно одну
произвольную нечётную цифру;— символ «*»
означает любую последовательность цифр
произвольной длины; в том числе «*» может
задавать и пустую последовательность.
• Например, маске 123*4?5 соответствуют
числа 123 415 и 12 300 475.
• Среди натуральных чисел, не превышающих 10^10,
найдите все числа, соответствующие
маске 5?34?71*2, делящиеся на 2026 без остатка.
• В ответе запишите все найденные числа в порядке
возрастания.

33. Задача 10

• 553497122
• 5134171692
• 5134971962
• 5734171592
• 5734971862

34. Поиск делителей

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

35. Поиск делителей

divs = []
for j in range(1, 36+1):
if i%j == 0:
divs.append(j)
print(divs)

36. Множества

• Множество - это «мешок», в котором хранятся только
уникальные элементы. У множеств нет порядка и нет
индексов (нельзя обратиться к элементу как s[0]).
• s = set() - создание
• s.add(x) – добавление
• s.discard(x) – удаление
• len(s) – количество
• Проверка if x in s: работает моментально, в отличие от
списков
• Так как в множестве нет порядка, перед печатью
ответа его нужно превратить в отсортированный
список. res = sorted(s)

37. Поиск делителей

divs = set()
for j in range(1, 36+1):
if i%j == 0:
divs.add(j)
print(divs) – Не будет повторов

38. Пример задачи

• Напишите программу, которая ищет среди целых
чисел, принадлежащих числовому отрезку
[210 235; 210 300], числа, имеющие ровно четыре
различных натуральных делителя, не считая единицы
и самого числа. Для каждого найденного числа
запишите эти четыре делителя в четыре соседних
столбца на экране с новой строки. Делители в строке
должны следовать в порядке возрастания.
• Например, в диапазоне [10; 16] ровно четыре
различных натуральных делителя имеет число 12,
поэтому для этого диапазона вывод на экране должна
содержать следующие значения:2 3 4 6

39. Решение

for i in range(210235,210300):
divs = set()
for j in range(2, i):
if i%j == 0:
divs.add(j)
if len(divs) == 4:
print(sorted(divs))
2 4 52561 105122
2 4 52567 105134
2 4 52571 105142

40. Метафора

• Любое число можно представить как площадь
прямоугольника, где стороны – делители.
• Например, для 36
6
36
1
2
1
18
6
18
2
4
12
9
3
9
4
3
12
36

41. Решение

for i in range(210235,210300):
divs = set()
for j in range(2, int(i**0.5)+1):
if i%j == 0:
divs.add(j)
divs.add(i//j)
if len(divs) == 4:
print(sorted(divs))
2 4 52561 105122
2 4 52567 105134
2 4 52571 105142

42. Задача 1

• Напишите программу, которая ищет среди целых
чисел, принадлежащих числовому отрезку
[110203; 110245], числа, имеющие ровно четыре
различных чётных натуральных делителя (при этом
количество нечётных делителей может быть любым).
Для каждого найденного числа запишите эти четыре
делителя в четыре соседних столбца на экране с новой
строки. Делители в строке должны следовать в порядке
возрастания.
• Например, в диапазоне [2; 16] ровно четыре чётных
различных натуральных делителя имеют числа 12 и 16,
поэтому для этого диапазона вывод на экране должна
содержать следующие значения:2 4 6 12
• 2 4 8 16

43. Задача 1

• Как проверять на чётность делители?
• Пример:
• 16
• 1, 2, 4, 8, 16
• Ловушка ЕГЭ: Делители ходят парами, но их чётность
может отличаться.
• Здесь единица нечётная, но её напарник чётный,
поэтому их надо проверять независимо.
if i % j == 0 and j % 2 == 0:
divs.add(j)
divs.add(i // j) # Ошибка! 16 не будет в
списке делителей

44. Решение

for i in range(110203,110245+1):
divs = set()
for j in range(1, int(i**0.5)+1):
if i%j == 0 and j%2==0:
divs.add(j)
if i%j == 0 and (i//j)%2==0:
divs.add(i//j)
if len(sorted(divs)) == 4:
2 4 55102 110204
print(sorted(divs))
2 14 15746 110222
2 6 36742 110226
2 22 10022 110242

45. Задача 2

• Напишите программу, которая ищет среди целых
чисел, принадлежащих числовому отрезку
[489 421; 489 440], числа, имеющие ровно четыре
различных натуральных делителя. Для каждого
найденного числа запишите эти четыре делителя в
четыре соседних столбца на экране с новой строки.
Делители в строке должны следовать в порядке
возрастания.
• Например, в диапазоне [12; 14] ровно четыре
различных натуральных делителя имеет число 14,
поэтому для этого диапазона вывод на экране должна
содержать следующие значения:1 2 7 14

46. Задача 3

• Напишите программу, которая ищет среди целых
чисел, принадлежащих числовому отрезку
[125 256; 125 330], числа, имеющие ровно шесть
различных чётных натуральных делителей. Для
каждого найденного числа запишите эти шесть
делителей в шесть соседних столбцов на экране с
новой строки. Делители в строке должны следовать в
порядке возрастания.
• Например, в диапазоне [2; 48] ровно шесть чётных
различных натуральных делителей имеют числа 24, 36
и 40, поэтому для этого диапазона вывод на экране
должна содержать следующие значения:2 4 6 8 12 24
• 2 4 6 12 18 36
• 2 4 8 10 20 40

47. Задача 4

• Напишите программу, которая ищет среди целых
чисел, принадлежащих числовому отрезку
[568 023; 569 230], число, имеющее максимальное
количество различных натуральных делителей, если
таких чисел несколько — найдите минимальное из них.
Выведите на экран количество делителей такого числа
и само число.Например, в диапазоне [2; 48]
максимальное количество различных натуральных
делителей имеет число 48, поэтому для этого
диапазона вывод на экране должн содержать
следующие значения:10 48

48. Ответы

• 2)
• 1 19 25759 489421
• 1 2 244711 489422
• 1 13 37649 489437
• 3)
• 2 6 18 13918 41754 125262
• 2 4 8 31322 62644 125288
• 2 6 18 13922 41766 125298
• 4)
• 144 568260

49. Простые числа

• Простые числа – числа, которые имеют 2 делителя:
• 1 и само число.
• Примеры:
• 2 (единственное чётное), 3, 5, 7, 11
• При этом 1 математически НЕ является простым
числом, так как один делитель.

50. Простые числа

• Как искать их в коде?
• Лучше всего написать отдельную функцию, которая:
• 1. Принимает число
• 2. Проверяет делители от 2 до корня числа
• 3. Если найден хоть один делитель: возвращать False
• 4. Если пройден весь цикл и не найден делитель:
возвращать True.

51. Простые числа

• def is_prime(number):
if n<2:
return False
for j in range(2, int(number**0.5)+1):
if number%j==0:
return False
return True
• print(is_prime(5)) True
• print(is_prime(8)) False
• print(is_prime(1)) False

52. Задача 5

• Напишите программу, которая ищет среди целых
чисел, принадлежащих числовому отрезку [2422000;
2422080], простые числа. Выведите все найденные
простые числа в порядке возрастания, слева от
каждого числа выведите его номер по порядку, считая,
что первое найденное число имеет номер 1, второе —
2 и так далее.

53. Задача 5

• def is_prime(number):
for j in range(2, int(number**0.5)+1):
if number%j==0:
return False
return True
• counter = 1
• for i in range(2422000, 2422080+1):
if is_prime(i):
print(counter, i)
counter+=1
1 2422027
2 2422033
3 2422037
4 2422073