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

Метод 1: метод грубой силы
Самый простой метод генерации простых чисел — использование метода грубой силы. Мы перебираем каждое число, начиная с 2, и проверяем, делится ли оно на любое число между 2 и квадратным корнем. Если оно не делится ни на какое число, то это простое число.

def is_prime_brute_force(n):
    if n < 2:
        return False
    for i in range(2, int(n  0.5) + 1):
        if n % i == 0:
            return False
    return True
def prime_generator_brute_force(limit):
    primes = []
    for num in range(2, limit):
        if is_prime_brute_force(num):
            primes.append(num)
    return primes

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

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

Метод 3: тест на простоту Миллера-Рабина
Тест на простоту Миллера-Рабина — это вероятностный алгоритм, широко используемый для определения того, является ли число простым. Он неоднократно применяет Малую теорему Ферма, чтобы проверить, является ли число составным или, возможно, простым. Несмотря на небольшую вероятность неправильной классификации составного числа как простого, он очень эффективен для больших чисел.

import random
def is_prime_miller_rabin(n, k=5):
    if n == 2 or n == 3:
        return True
    if n < 2 or n % 2 == 0:
        return False
    def check_composite(n, r, s, d):
        x = pow(r, d, n)
        if x == 1 or x == n - 1:
            return False
        for _ in range(s - 1):
            x = pow(x, 2, n)
            if x == n - 1:
                return False
        return True
    r, s = 0, n - 1
    while s % 2 == 0:
        r += 1
        s //= 2
    for _ in range(k):
        a = random.randrange(2, n - 1)
        if check_composite(n, a, s, r):
            return False
    return True
def prime_generator_miller_rabin(limit):
    primes = [2]
    for num in range(3, limit, 2):
        if is_prime_miller_rabin(num):
            primes.append(num)
    return primes

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