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

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

Простые числа — это натуральные числа больше единицы, которые делятся нацело только на единицу и на себя. Например, число 3 простое, так как нацело делится только на 1 и 3. Число 4 сложное, так как нацело делится не только на 1 и 4, но также на число 2.

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

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

from math import sqrt n = int(input()) prime = True i = 2 while i  sqrt(n): if n % i == 0: prime = False break i += 1 if prime: print("Простое число") else: print("Составное число") 

В программе мы сначала предполагаем, что введенное число n является простым, и поэтому присваиваем переменной prime значение True . Далее в цикле перебираются делители (переменная i ) от 2-х до квадратного корня из числа n . Как только встречается первый делитель, на который n делится без остатка, меняем значение prime на False и прерываем работу цикла, так как дальнейшее тестирование числа на простоту смысла не имеет.

Если после выполнения цикла prime осталась истиной, сработает ветка if условного оператора. В случае False , поток выполнения заходит в ветку else .

Если знать о такой особенности циклов в Python как возможность иметь ветку else , то код можно упростить, избавившись от переменной prime и ее проверки условным оператором после завершения работы цикла.

from math import sqrt n = int(input()) i = 2 while i  sqrt(n): if n % i == 0: print("Составное число") break i += 1 else: print("Простое число")

Ветка else при циклах (как while , так и for ) срабатывает, если в основном теле цикла не происходило прерывания с помощью break . Если break сработал, то тело else выполняться не будет. При использовании таких конструкций также следует помнить, что если условие в заголовке цикла сразу возвращает ложь (то есть тело цикла не должно выполняться ни разу), код тела else все-равно будет выполнен.

Программы выше будут определять числа 0 и 1 как простые. Это неправильно. Данные числа не являются ни простыми, ни сложными. Для проверки ввода пользователя, можно воспользоваться условным оператором или зациклить запрос числа, пока не будет введено корректное значение:

n = 0 while n  2: n = int(input())

Рассмотрим функцию, которая определяет, является ли число простым:

from math import sqrt def is_prime(n): i = 2 while i  sqrt(n): if n % i == 0: return False i += 1 if n > 1: return True a = int(input()) if is_prime(a): print("Простое число") else: print("Число НЕ является простым")

Здесь нет необходимости в прерывании работы цикла с помощью break , так как оператор return выполняет выход из тела всей функции.

Если цикл полностью отработал, выполнится выражение return True , находящееся ниже цикла. Оно помещено в тело условного оператора, чтобы исключить возврат «истины», когда в функцию передаются числа 0 или 1. В этом случае функция вернет объект None .

Программа не защищена от ввода отрицательного числа. При этом будет генерироваться ошибка на этапе извлечения квадратного корня.

Нарисуем блок-схему тестирования числа на простоту (без дополнительных проверок и оператора break ):

from math import sqrt n = int(input()) prime = True i = 2 while i  sqrt(n) and prime is True: if n % i == 0: prime = False i += 1 if prime: print("Простое число") else: print("Составное число")

—>

X Скрыть Наверх

Решение задач на Python

Найти все простые числа в заданном диапазоне

Привет всем.Помогите из задачей,пожалуйста, нужно написать на пайтоне.Помогите хотя-бы одной
3.Найти все простые числа в заданном диапазоне.

Лучшие ответы ( 1 )
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
Ответы с готовыми решениями:

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

Найти все простые числа в диапазоне от 2 до N
Напишите две программы, которые находят все простые числа в диапазоне от 2 до N двумя разными.

Задача: найти все простые числа в диапазоне
Вводятся два числа. Нужно найти все простые числа от A до B. Ограничение по времени — 1 секунда.

Найти все простые числа в заданном диапазоне
Найти все простые числа в промежутке между натуральными числами а и b (а > 2000, b — а ≥ 20)

Регистрация: 20.05.2013
Сообщений: 37

Сообщение было отмечено Marooo как решение

Решение

1 2 3 4 5 6 7 8 9 10

diapazon = int(input("Введите диапазон для поиска простых чисел: ")) for num in range(1,diapazon): count = 0 delitel = 2 while delitelnum: if num%delitel == 0: count += 1 delitel += 1 if count == 0: print (f' простое число')

Регистрация: 02.04.2014
Сообщений: 120
Я просто дополняю код под данное задание, наверное автор это сам смог сделать

1 2 3 4 5 6 7 8 9 10 11

diapazonn = int(input("Введите начало диапазона для поиска простых чисел: ")) diapazonk = int(input("Введите конец диапазона для поиска простых чисел: ")) for num in range(diapazonn, diapazonk): count = 0 delitel = 2 while delitel  num: if num % delitel == 0: count += 1 delitel += 1 if count == 0: print(f' простое число')

Регистрация: 23.11.2021
Сообщений: 38
Записей в блоге: 1

1 2 3 4 5

def prime(number): for i in range(2, number): if number % i == 0: return "Составное число" return "Простое число"

2421 / 1463 / 633
Регистрация: 01.11.2021
Сообщений: 2,266

1 2 3 4 5 6 7 8 9 10 11 12 13

def is_prime(num): if num == 2: return True if num  2 or num % 2 == 0: return False for i in range(3, int(num ** 0.5) + 1, 2): if not num % i: return False return True a, b = map(int, input("Два числа через пробел от a до b: ").split()) print(*list(filter(is_prime, range(a, b + 1))))

Регистрация: 06.11.2020
Сообщений: 1

1 2 3 4 5 6 7 8 9

diapoz = int(input()) konec_diapoz = int(input()) for i in range(diapoz, konec_diapoz): delitel = 0 for j in range(1, i + 1): if i % j == 0: delitel += 1 if delitel  2: print(i)

13179 / 6989 / 1471
Регистрация: 06.09.2009
Сообщений: 25,899
FaArtStem,
1. Не проверяете последнее число диапазона
2. Зачем-то проверяете четные числа
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
Помогаю со студенческими работами здесь

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

Найти все простые числа, лежащие в заданном диапазоне
Задача: Найти все простые числа, лежащие в заданном диапазоне. Простые числа – это числа больше 1.

Найти все простые числа в заданном диапазоне и вывести их на экран
Доброго времени суток! Есть задачка, есть кривое решение. 🙂 Суть задачки такова: найти все.

Процедуры или функции: Найти все простые числа,лежащие в заданном диапазоне и их сумму
Пользователь вводит два натуральных числа. Найти все простые числа,лежащие между ними и их сумму.

Найдите все простые делители целого числа в заданном диапазоне
Найдите все простые делители целого числа в заданном диапазоне.

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

Перебором делителей найти простые числа в указанном диапазоне, и вывести все простые числа в поле Memo
Мне нужна программка на Delphi, которая простым перебором делителей находит простые числа в.

Как найти простое число в списке?

Как можно найти простыe числa в последовательности десятичных, целых, отрицательных чисел и слов? я попробовал решить это таким образом:

def isPrime(n): if n % 2 == 0: return n == 2 d = 3 while d * d n print(isPrime(2.24)) 

и в данном примере выдает True, хотя 2.24 не простое число, то есть программа не рабочая и считает десятичные, отрицательные числа ВСЕ без исключения за простые А также выдает ошибку, когда встречает слово типа str()

Отслеживать
задан 4 дек 2020 в 11:20
17 8 8 бронзовых знаков

По определению простого числа — это натуральное число больше единицы. Натуральное число, в свою очередь, это целое число строго больше нуля. Поэтому ваш вопрос непонятен

4 дек 2020 в 11:25

@MaxU я знаю, но как исправить программу чтобы работала только для таких числ? просто она выполняет для всех числе в том числе отрицательных и десятичных

4 дек 2020 в 11:27

1 ответ 1

Сортировка: Сброс на вариант по умолчанию

1. проверить число на соответствие типу int

 if isinstance(n, int) is False: return False 

 value = abs(n) 

def isPrime(n): if isinstance(n, int) is False: return False value = abs(n) if value == 1: return False for i in range(2, int(value**0.5)): if value % i == 0: return False return True print(isPrime(2.24)) 

на счет отрицательных чисел — один момент с одной стороны конечно по определению простое число — это натуральное число строго большее 1, так что по идее надо проверку такую:

 if value  

return len([i for i in range(1, n + 1) if n % i == 0]) == 2