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

Метод 1: перебор
Метод перебора предполагает проверку делимости каждого числа в диапазоне от 2 до N-1. Если число не делится ни на одно число в этом диапазоне, оно считается простым.

def generate_primes_brute_force(n):
    primes = []
    for num in range(2, n + 1):
        is_prime = True
        for i in range(2, num):
            if num % i == 0:
                is_prime = False
                break
        if is_prime:
            primes.append(num)
    return primes

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

def generate_primes_sieve(n):
    sieve = [True] * (n + 1)
    sieve[0] = sieve[1] = False
    p = 2
    while p * p <= n:
        if sieve[p]:
            for i in range(p * p, n + 1, p):
                sieve[i] = False
        p += 1
    primes = [num for num, is_prime in enumerate(sieve) if is_prime]
    return primes

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

import math
def generate_primes_optimized(n):
    primes = []
    for num in range(2, n + 1):
        is_prime = True
        sqrt_num = math.isqrt(num)
        for i in range(2, sqrt_num + 1):
            if num % i == 0:
                is_prime = False
                break
        if is_prime:
            primes.append(num)
    return primes

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

import random
def is_prime_miller_rabin(n, k=5):
    if n <= 1:
        return False
    if n == 2 or n == 3:
        return True
    if n % 2 == 0:
        return False
    r, s = 0, n - 1
    while s % 2 == 0:
        r += 1
        s //= 2
    for _ in range(k):
        a = random.randint(2, n - 2)
        x = pow(a, s, 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
def generate_primes_miller_rabin(n):
    primes = [num for num in range(2, n + 1) if is_prime_miller_rabin(num)]
    return primes

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