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

Проблема 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 sieve0 (A,B):
  M = [1] * B
  M[0] = M[1] = 0
  for d in range(2, int(B**0.5) + 1):
    for i in range(2 * d,  B, d) :
      M[i] = 0
  return M  
A, B  = map(int, input().split())
t0 =prt()
P = sieve0(A,B+1)
k = sum(P[A:B+1])
print(f'Количество простых чисел на отрезке [{A};{B}] равно {k}. time = {prt() - t0}')

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

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

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

def sieve0(A,B):
  M = [1] * B
  M[0] = M[1] = 0
  for d in range(2, int(B**0.5) + 1):
    for i in range(2 * d,  B, d) :
      M[i] = 0
  return M  
def sieve1(A,B):
  M = [1] * B
  M[0] = M[1] = 0
  for d in range(2, int(B**0.5) + 1):
    if M[d] == 1 :
      for i in range(d * d,  B, d) :
        M[i] = 0
  return M  

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

Получим явное повышение эффективности (это можно замерить на отрозке от 1 до 10_000_000).
Добавим еще одно "логическое усовершенствование"
А почему вначале список M весь заполняется 1? Может быть исключить четные сразу

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

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

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

def sieve2(A,B):
  M = [0,0,1] + [1,0] * (B // 2)
  for d in range(3, int(B**0.5) + 1):
    if M[d] == 1 :
      for i in range(d * d,  B, d) :
        M[i] = 0
  return M  
def sieve3(A,B):
  M = [0,0,1] + [1,0] * (B // 2)
  for d in range(3, int(B**0.5) + 1):
    if M[d] == 1 :
      L = len(M[d*d: B: d])
      M[d*d : B:d] = [0]*L
  return M  

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

Итак, 1 фокус получился - результат увеличился в два раза.
Но, почему мы находили значение L как длину среза?
Можно ли это сделать через простое вычисление и ускорить работу программы?
Несложно понять, что L - это количество чисел полуинтервала [d²; B) кратных d
N([d²; B)) =N([0; B)) - N([0;d²) , где N([X;Y)) - количество чисел полуинтервала [X;Y) кратных d
Нетрудно понять, что N([0;d²) = d (это числа 0, d, 2d, ..., (d-1)d)
Также, можно проверить, что N([0; B)) равно B//i с округлением в большую сторону или
N([0; B)) = (B-1)//d + 1 = (B + d -1)//d = -(-B//d) (понять последнее сложнее, но для Python это верно)
Заменим L на -(-B // d + d) и создадим новую версию программы

def sieve3(A,B):
  M = [0,0,1] + [1,0] * (B // 2)
  for d in range(3, int(B**0.5) + 1):
    if M[d] == 1 :
      L = len(M[d*d: B: d])
      M[d*d : B:d] = [0]*L
  return M  
def sieve4(A,B):
  M = [0,0,1] + [1,0] * (B // 2)
  for d in range(3, int(B**0.5) + 1):
    if M[d] == 1 :
      M[d*d : B:d] = [0]* -(-B//d + d)
  return M  

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

Получили еще "хороший" прирост эффективности.
На отрезке от 10_000_000 до 20_000_000 он состовил более 25%
На этом пока остановимся и подведем итоги:

Эффективным методом получения/подсчёта чисел на отрезке (большом) может быть может быть метод решета Эратосфена
"Решето" можно изначально сформировать в "предсформированном" виде (здесь есть место для творчества)
Для "просеивания", вместо цикла, эффективнее использовать срезы

Ниже приведен вариант полученной программы, которая может за реальное время подсчитать количество простых чисел на отрезке [1; 100_000_000]

def sieve(A,B):
  M = [0,0,1] + [1,0] * (B // 2)
  for d in range(3, int(B**0.5) + 1, 2):
    if M[d] == 1 :
      M[d*d : B:d] = [0]* -(-B//d + d)
  return M  

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

Печать