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

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

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

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

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

import random
def miller_rabin(n, k=5):
    if n <= 1:
        return False
    if n <= 3:
        return True
    def check_composite(a, d, s, n):
        x = pow(a, 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
    d, s = n - 1, 0
    while d % 2 == 0:
        d //= 2
        s += 1
    for _ in range(k):
        a = random.randint(2, n - 1)
        if check_composite(a, d, s, n):
            return False
    return True

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