Оптимизированный алгоритм вывода всех простых чисел

Быстрый ответ

Наиболее оптимальным решением для данной задачи является решето Эратосфена. При его применении используется массив булевых значений, где состояние False присваивается составным числам. Простые числа затем добавляются в окончательный список следующим образом:

def get_primes(n):
    sieve = [True] * n
    primes = []
    for p in range(2, n):
        if sieve[p]:
            primes.append(p)
            for i in range(p * p, n, p):
                sieve[i] = False
    return primes

Чтобы получить все простые числа до N, достаточно вызвать функцию get_primes(N).

Разбор алгоритма

Решето Эратосфена — эффективный и одновременно простой метод поиска простых чисел до заданного N. Суть алгоритма заключается в последовательном отсеивании чисел, начиная со значения 2, присваивая составным числам значение не простые (False). На каждом шаге числа, кратные уже известным простым числам, игнорируются.

Уменьшение использования памяти вдвое

Воспользовавшись тем, что все четные числа, за исключением двойки, невозможно являются простыми, можно существенно уменьшить использование памяти, а также снизить вычислительные расходы примерно на 50%:

def get_primes_optimized(n):
    sieve = [False if i % 2 == 0 else True for i in range(n)]
    primes = [2]
    for p in range(3, n, 2):
        if sieve[p]:
            primes.append(p)
            for i in range(p * p, n, p * 2):
                sieve[i] = False
    return primes

Магия numpy

Библиотека Numpy позволяет ускорить генерацию простых чисел за счет оптимизированных операций с массивами. Использование типов массивов этой библиотеки предоставляет возможность осуществлять операции с большими объемами данных на высокой скорости, превосходя встроенные средства Python:

import numpy

def get_primes_numpy(n):
    sieve = numpy.ones(n // 2, dtype=bool)
    for i in range(3, int(n ** 0.5) + 1, 2):
        if sieve[i // 2]:
            sieve[i * i // 2::i] = False
    return numpy.r_[2, 2 * numpy.nonzero(sieve)[0][1::] + 1]

Визуализация

Все числа меньше N можно сравнить с клумбой:

Представим нашу клумбу как список, в котором:

• 🌱 обозначают составные числа (сорняки),
• 🌺 — простые числа (редкие и ценные цветы).

Решето Эратосфена можно считать работой внимательного садовника, который проходит по клумбе, отбирая простые числа (цветы), и эффективно удаляя сорняки (составные числа).

Другие методы поиска простых чисел

Несмотря на широкое применение решета Эратосфена, существуют и другие методы. К ним относятся решето Аткина и решето Сундарама.

Решето Аткина: старший брат

Решето Аткина имеет более высокую степень сложности и оптимизировано для использования с большим значением N. Этот алгоритм исключает ненужные числа, применяя более сложные алгоритмические подходы. Однако для его полного освоения может потребоваться серьезное знание математики.

Решето Сундарама: крайне эффективный но малоизвестный метод

Решето Сундарама — это элегантное решение, которое отсеивает составные числа, используя формулу i + j + 2*i*j для всех возможных i и j:

def sundaram3(max_n):
    numbers = list(range(3, max_n+1, 2))
    half = (max_n)//2
    initial = 4

    for step in range(3, max_n+1, 2):
        for i in range(initial, half, step):
            numbers[i] = 0
        initial += 2*(step+1)

        if initial > half:
            return [2] + [i for i in numbers if i]

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

Полезные материалы

1. Решето Эратосфена – Википедия
2. Решето Аткина – Википедия
3. itertools — Функции создания итераторов для эффективного циклического процесса — Документация Python 3.12.2
4. NumPy
5. Шпаргалка по сложности алгоритмов (Знай свои комплексности!) @ericdrowell
6. time — Время доступа и конвертации — Документация Python 3.12.2
7. Профайлеры Python — Документация Python 3.12.2