Простые числа веками интересовали математиков и компьютерщиков. От древних цивилизаций до современной криптографии — поиск эффективной идентификации простых чисел был предметом огромного интереса. В этой статье блога мы углубимся в мир алгоритмов простых чисел и исследуем их временную сложность. Мы обсудим различные методы, приведем примеры кода и прольем свет на самые популярные алгоритмы простых чисел, используемые сегодня.

1. Судебный отдел:

Метод пробного деления — самый простой способ определить, является ли число простым. Он включает в себя проверку делимости на все числа, меньшие заданного числа. Давайте посмотрим на код:

def is_prime_trial(n):
    if n < 2:
        return False
    for i in range(2, n):
        if n % i == 0:
            return False
    return True

Временная сложность: O(n)

2. Решето Эратосфена:

Решето Эратосфена — это древний алгоритм, который эффективно идентифицирует все простые числа до заданного предела. Он работает путем итеративной маркировки кратных каждого простого числа, начиная с 2. Вот пример реализации:

def sieve_of_eratosthenes(n):
    sieve = [True] * (n + 1)
    sieve[0] = sieve[1] = False
    for i in range(2, int(n  0.5) + 1):
        if sieve[i]:
            for j in range(i * i, n + 1, i):
                sieve[j] = False
    primes = [i for i in range(n + 1) if sieve[i]]
    return primes

Временная сложность: O(n log log n)

3. Тест на простоту Миллера-Рабина:

Тест Миллера-Рабина на простоту — это вероятностный алгоритм, который определяет, является ли данное число составным или, возможно, простым. Для выполнения теста он неоднократно применяет модульное возведение в степень. Вот упрощенная реализация:

import random
def miller_rabin(n, k=5):
    if n < 2:
        return False
    if n == 2 or n == 3:
        return True
    if n % 2 == 0:
        return False
    # Write n-1 as 2^r * d, where d is odd
    r, d = 0, n - 1
    while d % 2 == 0:
        r += 1
        d //= 2
    for _ in range(k):
        a = random.randint(2, n - 2)
        x = pow(a, d, n)
        if x == 1 or x == n - 1:
            continue
        for _ in range(r - 1):
            x = pow(x, 2, n)
            if x == n - 1:
                break
        else:
            return False
    return True

Временная сложность: O(k log n)

В заключение мы исследовали три популярных алгоритма простых чисел, а также их временную сложность. Метод пробного деления прост, но имеет временную сложность O(n), что делает его неэффективным для больших чисел. Решето Эратосфена более эффективно, его временная сложность составляет O(n log log n), что делает его пригодным для поиска простых чисел в заданном пределе. Наконец, тест на простоту Миллера-Рабина является вероятностным, но обеспечивает быстрый способ определения вероятных простых чисел с временной сложностью O(k log n).

Понимая временную сложность этих простых алгоритмов, программисты могут делать осознанный выбор, исходя из требований своих приложений. Помните, мир простых чисел огромен и сложен, и эти алгоритмы — лишь верхушка айсберга.