Алгоритм проверки Python Prime

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

Попробуйте в редакторе

Обзор

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

Самый неэффективный способ проверки простого числа — это итерация до самого числа. Мощная оптимизация заключается в проверке делимости только до квадратного корня числа.

Код и вывод выполнения

Эффективный алгоритм проверки простых чисел, демонстрирующий оптимизацию O(sqrt(n)).

prime_checker.py

Попробуйте в редакторе

import math

def is_prime(n):
    if n <= 1:
        return False
    if n == 2:
        return True
    if n % 2 == 0:
        return False
        
    max_divisor = math.isqrt(n)
    for i in range(3, max_divisor + 1, 2):
        if n % i == 0:
            return False
            
    return True

test_numbers = [2, 10, 17, 25, 97]
for num in test_numbers:
    status = "Prime" if is_prime(num) else "Not Prime"
    print(f"{num:2d} -> {status}")

Терминальный выход

 2 -> Prime
10 -> Not Prime
17 -> Prime
25 -> Not Prime
97 -> Prime

Пошаговая реализация

Криптография и алгоритмы хеширования
Учебная математика и теория сита
Внутренняя проверка безопасных ключей

Часто задаваемые вопросы

Зачем проверять только до квадратного корня?

Если $n = a\times b$, то хотя бы один из множителей ($a$ или $b$) должен быть меньше или равен квадратному корню из $n$. Таким образом, проверка выше является избыточной.

Связанные темы

Генератор последовательностей Фибоначчи Python

Запустите и поймите последовательность Фибоначчи на Python. В этом интерактивном примере кода показаны итеративные и рекурсивные подходы к созданию чисел Фибоначчи.

Алгоритмы сортировки Python

Изучите алгоритмы сортировки Python. Визуализируйте пузырьковую сортировку и сортировку слиянием в контексте IDE браузера.