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

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

import math
def is_prime(n):
    if n <= 1:
        return False
    for i in range(2, int(math.sqrt(n)) + 1):
        if n % i == 0:
            return False
    return True
# Usage example:
print(is_prime(21))  # Output: False

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

def sieve_of_eratosthenes(n):
    primes = [True] * (n + 1)
    primes[0] = primes[1] = False
    p = 2
    while p * p <= n:
        if primes[p]:
            for i in range(p * p, n + 1, p):
                primes[i] = False
        p += 1
    return primes[n]
# Usage example:
print(sieve_of_eratosthenes(21))  # Output: False

3. Тест на простоту Миллера-Рабина:
   Тестер на простоту Миллера-Рабина представляет собой вероятностный алгоритм, позволяющий определить простоту с высокой степенью точности. Он основан на концепции модульного возведения в степень и опирается на тест простоты Миллера-Рабина. Вот пример реализации на Python с использованием модуля random:

import random
def miller_rabin(n, k=5):
    if n <= 1:
        return False
    if n == 2 or n == 3:
        return True
    if n % 2 == 0:
        return False
    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 = n - 1
    s = 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
# Usage example:
print(miller_rabin(21))  # Output: False

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

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