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

Проблема L. Найди простое число на отрезке по его номеру

Проблема L. Найди на отрезке простое число по его номеру.

Дан отрезок [A;B и число K]. Надо среди всех простых чисел, принадлежащих отрезку, найти K-е простое число..
Входные умения: умение развернуть "решето Эратосфена", проверка на простоту с помощью "поиска минимального делителя числа" (программа min_del)
Задание:
написать программу, которая среди всех простых чисел отрезка находит К-е простое число
При подготовке тестов, считалось, что ученик может применить "неоптимальный" способ решения. На этом способе и тестировалась программа.
В каждом способе, вначале развертывалось "решето Эратосфена", а затем выполнялся поиск нужного числа.
Способ 1 Создать список из всех простых чисел отрезка, а затем выбрать нужное. На Python это можно сделать через срезы
Способ 2. Перебрать все числа отрезка в "решете" до подля каждого определить "простое оно или нет"
Программу sieve(A,B) для разветки решета скроем, отрезок зададим фиксированный, а номер числа будем вводить

# Способ 1
A, B  = 1580, 15801580
K = int(input()) #можно до 1_000_000
P = sieve(A,B+1)
t0 =prt()
X = [a for a in range(A,B+1) if P[a]]
L = len(X)
if K <= L :
  print(f'{K}-ое простое число на отрезке [{A};{B}] равно {X[K-1]}. time = {prt() - t0}')
else :
  print(f'Количество простых чисел на отрезке [{A};{B}] равно {L} Их не хватает. time = {prt() - t0}')

# Способ 2
A, B  = 1580, 15801580
K = int(input()) #можно до 1_000_000
P = sieve(A,B+1)
t0 =prt()
ans = - 1
cnt = 0
for i in range(A,B+1):
  if P[i] :
    cnt += 1
    if cnt == K :
      ans = i
      break
if ans > 0 :
  print(f'{K}-ое простое число на отрезке [{A};{B}] равно {ans}. time = {prt() - t0}')
else :
  print(f'Количество простых чисел на отрезке [{A};{B}] равно {cnt} Их не хватает. time = {prt() - t0}')

Способ 2 должен быть в целом лучше Способа 1 (нет лишних затрат памяти, перебераем меньше и т.п.),
но реальная ситуация интереснее

К из 1_018_852	Способ 1(мс)	Способ 2 (мс)
500_000	~720	~1000
600_000	~900	~1000
700_000	~1030	~1000
800_000	~1190	~1000
900_000	~1300	~1000
1_000_000	~1440	~1000
1_100_000	~1750	~1000

Возможно, результаты зависят от конкретной "песочницы", но получается, что

иногда, решение "неоптимальное" (способ 2) оказывается более эффеквным "оптимального" (способ 1)
"проще" дать более общее решение, а не "гоняться за мнимой эффективностью"

Печать