Вывести является ли число простым в Python

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

В этой статье мы рассмотрим несколько способов проверки числа на простоту в Python. Мы начнем с простого алгоритма, а затем рассмотрим более эффективные методы, которые позволяют проверить большие числа на простоту. Каждый способ будет подробно объяснен, и мы постараемся предоставить примеры кода, чтобы вы могли легко использовать эти методы в своих проектах.

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

Понятие простого числа и его свойства

Некоторые из основных свойств простых чисел:

  1. Простые числа начинаются с числа 2 и продолжаются бесконечно.
  2. Каждое натуральное число можно разложить на произведение простых чисел — это называется факторизацией.
  3. Если число n делится на простое число p без остатка, то это означает, что n также делится без остатка на все множители p.
  4. Если число p простое, то все его множители равны 1 и простому числу p.
  5. Простые числа обладают свойством уникальности: два различных простых числа не делятся без остатка друг на друга.

Понимание свойств простых чисел помогает в разработке эффективных алгоритмов проверки чисел на простоту и факторизации.

Алгоритм перебора делителей числа

Алгоритм перебора делителей числа заключается в следующих шагах:

  1. Выбираем число для проверки. Назовем его «n».
  2. Устанавливаем счетчик делителей в 0.
  3. Перебираем все числа от 1 до n.
  4. Если текущее число из перебора является делителем числа n, увеличиваем счетчик делителей на 1.
  5. По завершении перебора, если счетчик делителей равен 2, то число n является простым. Иначе, число n не является простым.

Алгоритм перебора делителей числа можно представить в таблице:

ШагДействиеРезультат
1Выбираем число для проверкиn
2Устанавливаем счетчик делителей в 00
3Перебираем все числа от 1 до n
4Если текущее число из перебора является делителем числа n, увеличиваем счетчик делителей на 1
5Если счетчик делителей равен 2, то число n является простымПростое
5Иначе, число n не является простымНе простое

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

Решето Эратосфена как эффективный способ проверки простоты числа

Процесс начинается с создания списка чисел от 2 до заданного числа n. Затем, начиная с 2-ки, каждое число, кратное 2, вычеркивается из списка. Затем берется следующее не вычеркнутое число, т.е. 3, и вычеркиваются все кратные 3 числа. Процесс повторяется, пока не будут вычеркнуты все кратные числа. Оставшиеся не вычеркнутыми числа считаются простыми.

Преимущество решета Эратосфена заключается в его скорости работы. Алгоритм имеет сложность O(n log log n), что делает его очень эффективным для больших чисел. Более того, решето Эратосфена может быть использовано для получения списка простых чисел в заданном диапазоне.

Ниже приведена таблица, демонстрирующая применение решета Эратосфена для проверки простоты числа 19:

Номер шагаЧислаВычеркнутые числа
12, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19
22, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 194, 6, 8, 10, 12, 14, 16, 18
32, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 194, 6, 8, 9, 10, 12, 14, 15, 16, 18
42, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 194, 6, 8, 9, 10, 12, 14, 15, 16, 18, 19

Как видно из таблицы, после выполнения всех шагов остается только одно число — 19, которое является простым. Это подтверждает, что число 19 — простое.

Использование встроенных функций Python для проверки простоты числа

Python предоставляет несколько встроенных функций, которые могут быть использованы для проверки простоты числа. Вот некоторые из них:

  • math.isqrt(n) — функция из модуля math возвращает наибольшее целое число, которое меньше или равно квадратному корню из числа n. Если n — простое число, то его квадратный корень будет вещественным числом, а значит, результат функции будет округлен до наибольшего целого числа, которое меньше этого вещественного числа.
  • math.factorial(n) — функция из модуля math возвращает факториал числа n. Если n — простое число, то его факториал будет равен n, так как факториал простого числа равен произведению всех чисел от 1 до n.
  • prime.isprime(n) — функция из модуля prime, которая возвращает True, если число n является простым, и False в противном случае. Эта функция основана на тесте на простоту Миллера-Рабина, который позволяет эффективно проверить простоту числа.

Пример использования этих функций для проверки простоты числа n:

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

В этом примере используется функция math.isqrt() для получения верхней границы цикла, функция prime.isprime() для проверки простоты числа, а также некоторые дополнительные проверки для исключения чисел, которые точно не являются простыми.

Использование этих встроенных функций Python позволяет эффективно проверить простоту числа и удостовериться в его достоверности.

Примеры кода для проверки простоты числа в Python

1. Перебор делителей:

Один из наиболее простых способов проверки простоты числа — перебор делителей этого числа. Мы можем перебрать все числа от 2 до n-1 и проверить, делится ли число на эти числа без остатка. Если числов делится без остатка на любое из этих чисел, значит оно не простое.


def is_prime(n):
if n <= 1:
return False
for i in range(2, n):
if n % i == 0:
return False
return True
num = 17
if is_prime(num):
print(num, "является простым числом")
else:
print(num, "не является простым числом")

2. Перебор делителей до корня числа:

Другим способом уменьшения количества делителей для проверки является перебор только до корня заданного числа. Если число делится нацело на какое-либо число от 2 до корня n, то оно также обязательно будет делиться нацело на какое-либо число от корня n до n-1.


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
num = 17
if is_prime(num):
print(num, "является простым числом")
else:
print(num, "не является простым числом")

3. Решето Эратосфена:

Третий подход — использование решета Эратосфена для нахождения всех простых чисел до заданного числа. Затем мы можем проверить, есть ли заданное число в полученном списке простых чисел.


def sieve_of_eratosthenes(n):
prime = [True for i in range(n+1)]
p = 2
while p**2 <= n:
if prime[p] == True:
for i in range(p**2, n+1, p):
prime[i] = False
p += 1
primes = []
for p in range(2, n+1):
if prime[p]:
primes.append(p)
return primes
num = 17
primes = sieve_of_eratosthenes(num)
if num in primes:
print(num, "является простым числом")
else:
print(num, "не является простым числом")

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

Оцените статью