Проверка на простое число

Решение: Проверка на простое число

Описание задачи

Требуется реализовать функцию для определения, является ли число простым (prime number). Простое число — это натуральное число, которое делится только на 1 и на само себя. Проверка простоты чисел — фундаментальная задача в программировании и криптографии, часто встречается в QA автоматизации при тестировании математических алгоритмов и валидации числовых данных.

Решение на Python

def is_prime(n):
    """
    Проверяет, является ли число простым.
    
    Args:
        n: целое число для проверки
    
    Returns:
        True, если число простое, False иначе
    """
    # Числа меньше 2 не являются простыми
    if n < 2:
        return False
    
    # 2 — единственное чётное простое число
    if n == 2:
        return True
    
    # Чётные числа (кроме 2) не являются простыми
    if n % 2 == 0:
        return False
    
    # Проверяем делители нечётные от 3 до sqrt(n)
    for i in range(3, int(n**0.5) + 1, 2):
        if n % i == 0:
            return False
    
    return True

Альтернативные подходы

1. Базовый метод (менее эффективный)

def is_prime_basic(n):
    """
    Простейший метод проверки делением на все числа до n.
    Временная сложность O(n) — неэффективно для больших чисел.
    """
    if n < 2:
        return False
    
    for i in range(2, n):
        if n % i == 0:
            return False
    
    return True

2. С использованием math.isqrt

import math

def is_prime_optimized(n):
    """
    Оптимизированный метод с использованием встроенной функции.
    Читаемее и может быть немного быстрее.
    """
    if n < 2:
        return False
    if n == 2:
        return True
    if n % 2 == 0:
        return False
    
    for i in range(3, math.isqrt(n) + 1, 2):
        if n % i == 0:
            return False
    
    return True

3. Решето Эратосфена (для множества чисел)

def sieve_of_eratosthenes(limit):
    """
    Находит все простые числа до limit.
    Используется когда нужно проверить много чисел.
    """
    if limit < 2:
        return []
    
    is_prime_arr = [True] * (limit + 1)
    is_prime_arr[0] = is_prime_arr[1] = False
    
    for i in range(2, int(limit**0.5) + 1):
        if is_prime_arr[i]:
            for j in range(i*i, limit + 1, i):
                is_prime_arr[j] = False
    
    return [i for i in range(2, limit + 1) if is_prime_arr[i]]

4. Тест Миллера-Рабина (для больших чисел)

def is_prime_miller_rabin(n, k=5):
    """
    Вероятностный тест для больших чисел.
    Используется в криптографии.
    """
    if n < 2:
        return False
    if n == 2 or n == 3:
        return True
    if n % 2 == 0:
        return False
    
    # Представляем n-1 как 2^r * d
    r, d = 0, n - 1
    while d % 2 == 0:
        r += 1
        d //= 2
    
    # Тест на k итерациях
    import random
    for _ in range(k):
        a = random.randrange(2, n - 1)
        x = pow(a, d, 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

Тестовые примеры

import unittest

class TestIsPrime(unittest.TestCase):
    
    def test_basic_prime(self):
        # Базовый случай из условия
        assert is_prime(7) == True
    
    def test_not_prime(self):
        # Не простое число из условия
        assert is_prime(10) == False
    
    def test_one(self):
        # 1 не является простым
        assert is_prime(1) == False
    
    def test_two(self):
        # 2 — единственное чётное простое число
        assert is_prime(2) == True
    
    def test_negative_number(self):
        # Отрицательные числа не являются простыми
        assert is_prime(-5) == False
    
    def test_even_numbers(self):
        # Все чётные числа (кроме 2) не простые
        assert is_prime(4) == False
        assert is_prime(6) == False
        assert is_prime(100) == False
    
    def test_known_primes(self):
        # Известные простые числа
        primes = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47]
        for p in primes:
            assert is_prime(p) == True, f'{p} должно быть простым'
    
    def test_known_non_primes(self):
        # Известные составные числа
        non_primes = [4, 6, 8, 9, 10, 12, 14, 15, 16, 18, 20, 21, 22, 24, 25]
        for np in non_primes:
            assert is_prime(np) == False, f'{np} не должно быть простым'
    
    def test_large_prime(self):
        # Большое простое число
        assert is_prime(97) == True
    
    def test_large_non_prime(self):
        # Большое составное число
        assert is_prime(100) == False

Анализ сложности

Применение в QA Automation

• Тестирование математических функций — проверка правильности алгоритмов работы с числами
• Валидация данных — проверка, соответствуют ли числа заданным критериям
• Граничные случаи — простые числа — частые edge cases
• Генерация тестовых данных — автоматическое создание наборов простых/составных чисел
• Performance тестирование — проверка скорости обработки больших чисел

Рекомендация

Для стандартного использования в QA рекомендуется оптимизированный метод до sqrt(n) — он обеспечивает хороший баланс между производительностью (O(√n)) и простотой. Для очень больших чисел используйте тест Миллера-Рабина, а для множества чисел — решето Эратосфена.