[Статья в блоге]

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

Метод №1: подход грубой силы
Давайте начнем с самого простого метода поиска простых чисел: подхода грубой силы. Мы можем перебрать все числа от 2 до заданного верхнего предела и проверить, делится ли каждое число на любое число, меньшее самого себя (исключая 1). Если число не делится ни на какое меньшее число, оно простое. Вот фрагмент кода на Python:

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

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

def sieve_of_eratosthenes(limit):
    sieve = [True] * (limit + 1)
    sieve[0] = sieve[1] = False
    for i in range(2, int(limit0.5) + 1):
        if sieve[i]:
            for j in range(i * i, limit + 1, i):
                sieve[j] = False
    primes = []
    for i in range(2, limit + 1):
        if sieve[i]:
            primes.append(i)

    return primes
def print_primes(limit):
    primes = sieve_of_eratosthenes(limit)
    for prime in primes:
        print(prime)

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

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

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