Вычислительные методы в дискретной математике
О сложности построения таблицы простых чисел на машине Тьюринга
И. С. Сергеев ФГУП "НИИ "Квант", г. Москва, Россия
Аннотация:
Доказывается, что сложность построения таблицы простых чисел от
$1$ до
$n$ на многоленточной машине Тьюринга равна O
$(n\log n)$.
Ключевые слова:
машина Тьюринга, сложность, просеивание.
УДК:
519.71
DOI:
10.17223/20710410/31/8
Реферативные базы данных:
© , 2024
Полный текст:
PDF файл (645 kB)