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

Проблема K. Количество простых чисел на отрезке

Проблема K. Количество простых чисел на отрезке.

Дан отрезок [A;B]. Надо определить сколько простых чисел принадлежит отрезку.
Входные умения: проверка на простоту с помощью "поиска минимального делителя числа" (программа min_del)
Задание:
написать функцию count_prime(A, B), которая возвращает число простых чисел на отрезке
Способ 1 - перебрать все числа отрезка, для каждого определить "простое оно или нет"

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
def check(n) :
  if n == min_del(n) : return 1
  return 0
def count_prime (A,B):
  ans = 0
  if A == 1 : A = 2
  for n in range(A, B+1):
    ans += check(n)
  return ans  
A, B  = map(int, input().split())
t0 =prt()
k = count_prime(A,B)
print(f'Количество простых чисел на отрезке [{A};{B}] равно {k}. time = {prt() - t0}')

Можно убедиться, что программа работает для A,B таких, что B-A не очень велико.
Для альтернативного способа можно предложить использование метода "решето Эратосфена", но не объяснять как его реализовать эффективно.
Возьмет описание из интернета:

Для нахождения всех простых чисел не больше заданного числа n, следуя методу Эратосфена, нужно выполнить следующие шаги:

Выписать подряд все целые числа от двух до n (2, 3, 4, ..., n).
Пусть переменная p изначально равна двум — первому простому числу.
Зачеркнуть в списке числа от 2p до n, считая шагами по p (это будут числа, кратные p: 2p, 3p, 4p, ...).
Найти первое незачёркнутое число в списке, большее чем p, и присвоить значению переменной p это число.
Повторять шаги 3 и 4, пока возможно.

Возможно ученик его реализует "дословно". Приведем примерное решение.
Программа sieve0(A,B) получает границы полуинтервала [A, B) и
возвращает список из B элементов, таких что: B[p] = 1 если p - простое и 0 -в противном случае

def sieve_0 (N):
  M = [1] * (N+1)
  M[0] = M[1] = 0
  for d in range(2, N):
    for i in range(2 * d,  N, d) :
      M[i] = 0
  return M  
A, B  = map(int, input().split())
t0 =prt()
P = sieve_0(B+1)
print(f'Развертка Решета до {B} заняла time = {prt() - t0}')
k = sum(P[A:B+1])
print(f'Количество простых чисел на отрезке [{A};{B}] равно {k}. ')

Можно убедиться, что на отрезке [1,1000007] решето уже дает большой выигрыш во времени.
Теперь можно приступить к этапу "повышение эффективности программ".
Для этого ещё раз "понять":

что 4 мы тоже "пытаемся вычеркивать". Значит надо добавить проверку d (делителя) на простоту
то есть добавить условие M[d] == 1

Внесем это изменение и проверим прирост "эффективности", сравнив решения sieve_0 и sieve_1 можно увидеть в таблице в конце тетради
(сравниваем только развертывание решета, без подсчета количества простых)

def sieve_1(N):
  M = [1] * (N + 1)
  M[0] = M[1] = 0
  for d in range(2, N):
    if M[d] == 1 :
      for i in range(2 * d,  N, d) :
        M[i] = 0
  return M  

A, B  = map(int, input().split())
t0 =prt()
P = sieve_1(B+1)
print(f'Развертка Решета до {B} заняла time = {prt() - t0}')
k = sum(P[A:B+1])
print(f'Количество простых чисел на отрезке [{A};{B}] равно {k}. ')

Получим явное повышение эффективности (примерно в 5 раз).
Добавим еще одно "логическое усовершенствование".
Вычеркивание начиналось с 2d. Однако, несложно убедиться, что его можно начинать с d*d,
и так как, d*d должно быть меньше N, то d можно перебирать только до корня из N
Внесем и эти изменения

def sieve_2(N):
  M = [1] * (N + 1)
  M[0] = M[1] = 0
  for d in range(2, int(N ** 0.5 + 1)):
    if M[d] == 1 :
      for i in range(d * d,  N, d) :
        M[i] = 0
  return M  

A, B  = map(int, input().split())
t0 =prt()
P = sieve_2(B+1)
print(f'Развертка Решета до {B} заняла time = {prt() - t0}')
k = sum(P[A:B+1])
print(f'Количество простых чисел на отрезке [{A};{B}] равно {k}. ')

Получили новое повышение эффективности (примерно в 2 раза).
Перебор d идет с шагом 1, но можно сделать с шагом 2, так как у нас только одно простое четное число.
Попробуем обработать d = 2 на этапе инициализации списка M
Внесем и эти изменения

def sieve_3(N):
  M = [0, 0, 1] + [1, 0] * (N // 2)
  for d in range(3, int(N ** 0.5 + 1), 2):
    if M[d] == 1 :
      for i in range(d * d,  N, d) :
        M[i] = 0
  return M  

A, B  = map(int, input().split())
t0 =prt()
P = sieve_3(B+1)
print(f'Развертка Решета до {B} заняла time = {prt() - t0}')
k = sum(P[A:B+1])
print(f'Количество простых чисел на отрезке [{A};{B}] равно {k}. ')

Получили небольшое, но повышение эффективности (примерно на 10%).
Ещё можно заметить, что перебор идет только по нечетным d и вычеркивать можно только на нечётных позициях,
а значит шаг для вычеркивания можно сделать чётным, то есть равным 2d
Внесем и эти изменения

def sieve_4(N):
  M = [0, 0, 1] + [1, 0] * (N // 2)
  for d in range(3, int(N ** 0.5 + 1), 2):
    if M[d] == 1 :
      for i in range(d * d,  N, 2 * d) :
        M[i] = 0
  return M  

A, B  = map(int, input().split())
t0 =prt()
P = sieve_4(B+1)
print(f'Развертка Решета до {B} заняла time = {prt() - t0}')
k = sum(P[A:B+1])
print(f'Количество простых чисел на отрезке [{A};{B}] равно {k}. ')

Теперь повышение эффективности более внушительное (решение sieve_2 улучшено почти в два раза)
Кажется, что улучшений больше нет, но это логических.
Теперь "технические" тонкости или "фишки Python"
Применим следующий прием: "замене изменения элементов списка в цикле" на "замену среза "
for i in range(d * d, B, 2 * d) : M[i] = 0
заменим на M[d*d:B:2 * d ] = [0] * len(range(d * d, B, 2 * d))
Внесем эти изменения

def sieve_5(N):
  M = [0, 0, 1] + [1, 0] * (N // 2)
  for d in range(3, int(N ** 0.5 + 1), 2):
    if M[d] == 1 :
      dd, d2 = d * d, 2 * d
      M[dd: N : d2] = [0] *len(range(dd, N, d2))
  return M  

A, B  = map(int, input().split())
t0 =prt()
P = sieve_5(B+1)
print(f'Развертка Решета до {B} заняла time = {prt() - t0}')
k = sum(P[A:B+1])
print(f'Количество простых чисел на отрезке [{A};{B}] равно {k}. ')

Итак, 1 фокус получился - результат увеличился в два раза.
Может быть len(range(d*d, B, 2*d) считается медленно и надо придумать формулу?
Это несложно сделать, если понять/проверить, что
len(range(a, b, c) = -(-(b-a)//c)
Ради интереса, проверим это, создав новую версию программы

def sieve_6(N):
  M = [0, 0, 1] + [1, 0] * (N // 2)
  for d in range(3, int(N ** 0.5 + 1), 2):
    if M[d] :
      dd, d2 = d * d, 2 * d
      L = -(-(N-dd)//d2)
      M[dd: N : d2] = [0] * L
  return M  

A, B  = map(int, input().split())
t0 =prt()
P = sieve_6(B+1)
print(f'Развертка Решета до {B} заняла time = {prt() - t0}')
k = sum(P[A:B+1])
print(f'Количество простых чисел на отрезке [{A};{B}] равно {k}. ')

Замена вычисления len(range(...)) похоже прироста эффективности не дает, а код усложняет.
На этом пока остановимся и подведем итоги:

Эффективным методом получения/подсчёта чисел на отрезке (большом) может быть может быть метод решета Эратосфена
"Решето" можно изначально сформировать в "предсформированном" виде (здесь есть место для творчества)
Для "просеивания", вместо цикла, эффективнее использовать срезы, вычисляя размер среза используя len(range ...)
Попытка использовать константы True/False на Python "выигрыша" не дает (см. решение ниже)
Программа развертывания "решета Эратосфена" занимает 7 простых строк кода, работает достаточно быстро,
поэтому метод "решета" может быть использован при решении большого класса задач

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

	1_000_000(мс)	10_000_000(сек)	100_000_000 (сек)
sieve_0	720	15,350	-
sieve_1	190	3,0	-
sieve_2	93	1,53	20,75
sieve_3	78	1,3	16,3
sieve_4	48	0,78	9,5
sieve_5	16	0,25	3,0

def sieve(N):
  M = [False, False, True] + [True, False] * (N // 2)
  for d in range(3, int(N ** 0.5 + 1), 2):
    if M[d] :
      dd, d2 = d * d, 2* d 
      M[dd: N : d2] = [False] *len(range(dd, N, d2))
  return M  

A, B  = map(int, input().split())
t0 =prt()
P = sieve(B+1)
print(f'Развертка Решета до {B} заняла time = {prt() - t0}')
k = sum(P[A:B+1])
print(f'Количество простых чисел на отрезке [{A};{B}] равно {k}. ')

Печать