Перейти к содержимому

Как проверить число на простоту в 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 

Похожие записи:
  1. Сериализаторы для связанных моделей
  2. Kittygram 2: новые возможности
  3. Определить количество введенных простых чисел
  4. Django — доработка шаблона формы регистрации
Добавить комментарий Отменить ответ

Эта книга является вашим путеводителем по JavaScript, охватывающим лучшие практики для написания чистого и

Эта книга о том, как продвигать большие сложные проекты. Здесь рассмотрено SEO в самом

Курс знакомит с теоретическим наследием в области медиа, обучает основным подходам к теоретическому анализу

Курс знакомит с теоретическим наследием в области медиа, обучает основным подходам к теоретическому анализу

Курс знакомит с теоретическим наследием в области медиа, обучает основным подходам к теоретическому анализу

Курс знакомит с теоретическим наследием в области медиа, обучает основным подходам к теоретическому анализу

Курс знакомит с теоретическим наследием в области медиа, обучает основным подходам к теоретическому анализу

Проверка числа на простоту с помощью перебора делителей, Python 3

Задача
Написать функцию, принимающую 1 аргумент — натуральное число, и возвращающую True, если оно простое, и False - иначе.
Решение
Поиск алгоритма проверки числа на простоту дал довольно несложную методику перебора делителей от 2 до округленного квадратного корня данного числа. С помощью range(2,math.ceil(math.sqrt(a))+1) мы создаем набор делителей для проверки. Условием math.fmod(a,i) < tol мы проверяем делится ли данное число на текущий делитель без остатка. Пример применения функции дан после ее определения, проверить можно непосредственно.

# fluxoid, ifi@yandex.ru # 27.6.2017 # Решаем задачу перебором делителей # функция возвращает 1 если число простое # и 0 если составное import math def is_prime(a): tol=1e-3 if a==2: return 1 for i in range(2,math.ceil(math.sqrt(a))+1): # перебор делителей в цикле if math.fmod(a,i)  tol: # составное число return 0 else: # простое число return 1 # Определим все простые числа от x1 до x2 x1=1 x2=100 for i in range(x1,x2): if is_prime(i)==1: print('%d - простое число' % i); 

Метки: python, программирование, решение задач

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

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

25 августа 2023

· Обновлено 8 ноября 2023

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

Научим детей и подростков программировать на 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 и поделись крутым результатом с друзьями

Стартуй в программировании прямо сейчас

Улучшенный наивный метод

Мы можем оптимизировать перебор:

  1. Проверяем, делится ли число на 2.
  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.

Решение задачи Проверка числа на простоту с Яндекс Контест

Дано натуральное число n>1. Проверьте, является ли оно простым. Программа должна вывести слово YES, если число простое и NO, если число составное. Решение оформите в виде функции IsPrime(n), которая возвращает True для простых чисел и False для составных чисел. Решение должно иметь сложность .

Код

Скопировать код

def IsPrime(n): for i in range(2, int(n ** 0.5) + 1): if n % i == 0: print("NO") return print("YES") n = int(input()) IsPrime(n) 
         

Автор: Администратор

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *