Q: Алгоритм Эратосфена в его классическом изложении достаточно трудоёмкий (чрезмерно большое число сравнений). Для его оптимизации можно предпринять:
1. Начальный ряд можно выписать только для нечётных чисел, дополнив его в начале цифрой 2 как единственно чётным простым: (2, 3, 5, 7, …, n).
2. На шаге № 3 числа можно зачеркивать начиная сразу с числа p2, потому что все составные числа меньше него уже будут зачеркнуты к этому времени.
3. И, соответственно, останавливать алгоритм можно, когда p2 станет больше, чем n.
4. Также, все p большие чем 2 — нечётные числа, и поэтому для них можно считать шагами по 2*p (а не p), начиная с p2.
Реализуйте оптимизированный алгоритм.
A: Оптимизированный алгоритм Эратосфена, позволяющий уменьшить число «отсеиваний» на несколько порядков:
Код: Выделить всё
#!/usr/bin/python3
def aristofn(n:int) -> list:
a = [2]
a.extend([i for i in range(3, n, 2)])
i = 1
while True:
try:
p = a[i]
if p * p > n:
break
except IndexError:
break
for j in range(p * p, n, 2 * p):
if j in a: a.remove(j)
i += 1
print('шагов просеивания: ', i)
return a
while(True):
try:
d = int(input('число: '))
except ValueError:
print('ошибка: не целое положительное число!')
continue
except (KeyboardInterrupt, # ^C
EOFError): # ^D - EOF
print('\rзавершение работы')
exit()
else:
print(d, ":", *aristofn(d))
Код: Выделить всё
olej@R420:~/2021/own.BOOKs/tasks-Python/DRAFT$ ./aristofn.py
число: 55
шагов просеивания: 4
55 : 2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53
число: 100
шагов просеивания: 4
100 : 2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97
число: 300
шагов просеивания: 7
300 : 2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 101 103 107 109 113 127 131 137 139 149 151 157 163 167 173 179 181 191 193 197 199 211 223 227 229 233 239 241 251 257 263 269 271 277 281 283 293
завершение работы
