Статья Автор: Лебедев Дмитрий Алексеевич

Проблема A. Является ли число простым

Этой статьей начинается блок материалов, посвященный обучению программированию на примерах одной задачи.
Предположим. что есть задача, которую ученик решил (считает, что решил). Что дальше?
Надо создать условия, чтобы после решения задачи ученик поставил перед собой несколько вопросов:

Можно ли решить задачу более эффективно
Что "ещё можно получить" из решения данной задачи
Зачем я решал данную задачу

При постановке заданий будем считать, что ученик владеет "основными навыками программировани" (условные операторы, циклы, подпрограммы), но "плохо ориентируется в алгоритмических методах" (определение сложности алгоритма, структурах и методах).

Проблема A. "Является ли число простым"

На входе ученик знает, что простое число это - число, большее 1 и делиться только на 1 и само себя"
Поставим перед учеником задачу:

Написать подпрограмму is_prime(n), которая проверяет, является ли число простым.

Ниже приведен "ожидаемый результат"

def is_prime(n):
  if n <= 1: 
    return False
  for i in range(2, n) :
    if n % i == 0 : 
      return False
  return True
n = int(input())
print(is_prime(n))

Следующим этапом может быть предложение пройти тесты задачи или проверить своё решиния для достаточно большого числа
(например 10⁹ + 7) и подойти к решению "до корня".
Это можно сделать, основавываясь на следующих "посылках":

число простое, если оно больше 1 и не составное
пусть n = a·b и a <= b, тогда a2 <= a·b = n
значит, если n - составное тогда и только тогда, когда у него есть делитель, квадрат которого не превосходит n

На основе этого можно модифицировать стандартное решение и сравнить его с предыдущим
(желательно с использование таймеров)

def is_prime0(n):
  if n <= 1: 
    return False
  for i in range(2, n) :
    if n % i == 0 : 
      return False
  return True
def is_prime1(n):
  if n <= 1: 
    return False
  for i in range(2, int(n**0.5) +1) : #так пишет большинство учеников
    if n % i == 0 : 
      return False
  return True
k = int(input())
n = get_prime(10**k) # получает простое число не меньшее 10**k
t0 =prt()
print(f'{n} is prime? {is_prime0(n)}. time = {prt() - t0} (способ 0)')
t0 =prt()
print(f'{n} is prime? {is_prime1(n)}. time = {prt() - t0} (способ 1)')

Видим, что при больших числах "способ 0" теряет смысл, а "способ 1" работает
Забыли про "способ 0" и станем оценивать "способ 1"

Можно обсудить "принцип полезного вывода" и понять, "что заставляет" выводить False
- ответ: нахождение делителя числа
- вопрос: какого ?
- ответ: первого
- вопрос: первый - это какой?
если получим ответ "минимальный", то диалог состоялся
Можно дать вспомогательныю задачу "найти минимальный делитель числа больший 1",
а если его нет, то вернуть число
Теперь можно задаться вопросами:
- минимальный собственный делитель числа - простое число?
- если число больше 1, можно ли по минимальному делителю узнать "число простое или нет"

Результатом этой работы должна стать программа
min_del(n) - возвращающая минимальный делитель числа (1 для 1) и проверка
if n == min_del(n) and n > 1 : print(f'{n} is prime')
else : print(f'{n} not is prime')
Напишем программу min_del (n) и программу проверки на простоту на базе неё
(можно написать базу совместно с учениками)
Сравним решения на произвольных простых числах (способ 1 "спрячем")

def is_prime2(n):
  if n <= 1: 
    return False
  if n == min_del(n) : return True
  return False
def min_del(n):
  if n == 1: return 1
  for d in range(2, int(n**0.5) + 1):
    if n % d == 0 : return d
  return n
k = int(input())
n = get_prime(10**k) # получает простое число не меньшее 10**k
t0 =prt()
print(f'{n} is prime? {is_prime1(n)}. time = {prt() - t0} (способ 1)')
t0 =prt()
print(f'{n} is prime? {is_prime2(n)}. time = {prt() - t0} (способ 2)')

При такой версии "способ 2" не лучше "способа 1".
Зададимся вопросом: Как устроены простые числа?
Увидим, что из простых четным является только 2 !!!
Значит если проверить 2, то дальше можно идти с шагом 2.
Модифицируем "способ 2" (вернее программу min_del(n) )
На "больших значениях" (k>10) увидим прирост скорости для "способа 2" в пару раз

def is_prime2(n):
  if n <= 1: 
    return False
  if n == min_del(n) : return True
  return False
def min_del(n):
  if n == 1: return 1
  if n % 2 == 0: return 2
  for d in range(3, int(n**0.5) + 1, 2):
    if n % d == 0 : return d
  return n
k = int(input())
n = get_prime(10**k) # получает простое число не меньшее 10**k
t0 =prt()
print(f'{n} is prime? {is_prime1(n)}. time = {prt() - t0} (способ 1)')
t0 =prt()
print(f'{n} is prime? {is_prime2(n)}. time = {prt() - t0} (способ 2)')

Подведем итог:

"Базовым кирпичеком" метода проверки числа на простоту будет программа
"поиска минимального делителя
Поиск минимального делителя пригодиться в дальнейшем для
- для решения задачи факторизации
- подсчета числа делителей
- подсчета суммы делителей
При анализе "Проблемы А" познакомили учеников с
- методом полезного возврата
- постепенным повышением эффективности

Ниже приведен более удобный код программы для "способа 2"

def min_del(n):
  if n % 2 == 0: return 2
  if n < 9: return n
  for d in range(3, int(n**0.5) + 1, 2):
    if n % d == 0 : return d
  return n
n = int(input())
#n = get_prime(0**k) # получает простое число не меньшее 10**k
m = min_del(n)
t0 =prt()
print(f'{n} is prime? {(m == n) and (n > 1)}. time = {prt() - t0}')

Печать