Временная сложность алгоритмов простых чисел относится к вычислительной эффективности алгоритмов, используемых для определения того, является ли данное число простым или нет. Вот несколько часто используемых простых алгоритмов с указанием их временной сложности:
-
Судебный отдел:
- Временная сложность: O(√n)
- Описание: В этом методе заданное число делится на все числа от 2 до √n. Если какое-либо из делений дает целое частное, то число не является простым.
-
Решето Эратосфена:
- Временная сложность: O(n log log n)
- Описание: Этот алгоритм генерирует все простые числа до заданного предела (n). Он итеративно помечает кратные каждого простого числа как составные, тем самым идентифицируя все простые числа.
-
Тест на простоту Миллера-Рабина:
- Временная сложность: зависит от количества итераций (k)
- Описание. Тест Миллера-Рабина – это вероятностный алгоритм, который определяет, является ли данное число простым. Временная сложность зависит от количества выполненных итераций.
-
Тест на примитивность AKS:
- Временная сложность: O(n^6)
- Описание. Тест AKS представляет собой детерминированный алгоритм, который определяет, является ли данное число простым. Однако он широко не используется из-за высокой временной сложности.