Как проверить простое ли число Python 3
Оптимизированный алгоритм поиска простых неотрицательных чисел:
- проверить на 0 и 1
- проверить на чётность и равенство 2 (исключается ~50% чисел)
- проверить на кратность 3 и равенство 3 (исключается ещё ~33% чисел)
- для проверки оставшихся чисел воспользоваться формулой 6n ± 1 (при n = 1, простыми будут 5 и 7, при n = 2: 11 и 13, и т.д.)
- как отмечено раньше, проверять делители следует до корня из заданного числа
def is_prime(num): prime = num > 1 and (num % 2 != 0 or num == 2) and (num % 3 != 0 or num == 3) i = 5; d = 2; while prime and i * i print(*[ i for i in range(101) if is_prime(i)]) >> 2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 Отслеживать
ответ дан 30 дек 2021 в 23:46
Nowhere Man Nowhere Man
15.3k 28 28 золотых знаков 19 19 серебряных знаков 29 29 бронзовых знаков
Вот моё решение:
def is_prime(x): for i in range(2, (x//2)+1): if x % i == 0: return False return True Оно простое, лакониченое и оптимизированное. Цикл перебирает возможные делители числа от двойки до половины проверяемого числа, ибо проверять числа дальше просто нет смысла, так как любое лисло нацело делится максимум на половину себя.
Проверка на простое число в Python
Проверка на простое число часто встречается в задачах по математике и программировании. Простое число — это число, которое делится только на 1 и на себя. В этой статье мы рассмотрим несколько методов проверки на простое число с использованием Python.
25 августа 2023
· Обновлено 8 ноября 2023
Научим детей и подростков программировать на Python
Поможем освоить самый востребованный язык программирования в мире и создать первые реальные проекты
Наивный метод
Простейший способ проверки — перебор всех чисел до корня из исследуемого числа.
def is_prime(n):
if n return False
for i in range(2, int(n**0.5) + 1):
if n % i == 0:
return False
return True
Стартуй в программировании прямо сейчас
Реши свою первую настоящую задачу на JavaScript и поделись крутым результатом с друзьями
Улучшенный наивный метод
Мы можем оптимизировать перебор:
- Проверяем, делится ли число на 2.
- Если не делится, то перебираем только нечётные делители.
Выберите идеального наставника по программированию
15 000+ проверенных преподавателей со средним рейтингом 4,8. Учтём ваш график и цель обучения
Тест Ферма
Тест Ферма основан на малой теореме Ферма. Этот метод не дает гарантированного ответа, но позволяет с высокой вероятностью определить простоту числа. k=5 в алгоритме — это количество итераций теста Ферма, чем больше это число, тем больше вероятность, что число действительно простое.
import random
def fermat_test(n, k=5):
if n return False
for _ in range(k):
a = random.randint(1, n-1)
if pow(a, n-1, n) != 1:
return False
return True
Тест Миллера-Рабина
Это вероятностный тест, который позволяет с высокой точностью определить простоту числа, особенно для больших чисел. k=5 в алгоритме — это количество итераций теста Миллера-Рабина, чем больше это число, тем больше вероятность, что число действительно простое.
import random
def miller_rabin_test(n, k=5):
if n return False
if n return True
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
Есть множество методов проверки простоты числа. Выбор метода зависит от конкретной задачи. Для больших чисел рекомендуется использовать вероятностные тесты, такие как Ферма или Миллера-Рабина.
С помощью приведенных выше методов можно эффективно определить, является ли данное число простым, используя Python.
Функция проверки числа на простоту
Напишите функцию, которой принимает натуральное число и определяет, является ли это число простым или сложным.
from math import sqrt def is_prime(n): # Если число меньше двух, то оно ни простое, ни сложное. if n < 2: return False # Число 2 является простым. if n == 2: return True # Верхняя граница делителей. limit = sqrt(n) # Нижняя граница делителей. i = 2 while i
Похожие записи:
- Сериализаторы для связанных моделей
- Kittygram 2: новые возможности
- Определить количество введенных простых чисел
- Django — доработка шаблона формы регистрации
Какая функция нужна для нахождения простого числа в Python?
Для начала определимся с определением. Простое число - натуральное число, имеющее ровно два различных натуральных делителя: 1 и самого себя.
Напишем функцию, принимающую на вход число и проверяющую, является ли оно простым.
import math def is_prime(number): # список простых чисел начинается с 2, всё остальное можно сразу отмести if number 1: return False number_sqrt = int(math.sqrt(number)) divisors = range(2, (number_sqrt + 1)) # Если число не простое, то в отрезке от 1 до квадратного корня числа, точно будут его делители. for element in divisors: if number % element == 0: return False return True is_prime(0) # False is_prime(1) # False is_prime(2) # True is_prime(3) # True is_prime(4) # False
