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

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

  • автор:

Найти простые числа

Author24 — интернет-сервис помощи студентам

По введенным числам A и B вывести все простые числа в интервале от A до B включительно.

Входные данные:
В единственной строке вводятся два числа 1 ≤ A ≤ B ≤ 500000

Выходные данные:
Вывести в одну строку все простые числа в интервале от A до B включительно

Примеры:
входные данные
2 2
выходные данные
2
—————————-
входные данные
1 100
выходные данные
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
———————————————
———————————————
Примечание: минимальное простое число — 2.

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

Как найти простые числа в диапазоне?
Здравствуйте! Вы не могли бы сказать, как с помощью решета Эратосфена можно найти простые числа в.

Найти все трехзначные простые числа
Найти все трехзначные простые числа(простым называется натуральное число, большее 1, не имеющее.

Как найти простые делители для числа?
Всем привет. Подскажите как для числа найти простые делители?

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

Найти все простые числа, сумма цифр которых больше 35
Для интервала найти все простые числа, сумма цифр которых больше 35. Запишите шестое найденное (по.

1103 / 689 / 306
Регистрация: 05.09.2021
Сообщений: 1,202
NebraskKrasnod,

1 2 3 4 5 6 7 8 9 10 11
def is_prime(n): if n  2: return False for i in range(2, n // 2 + 1): if n % i == 0: return False return True a, b = map(int, input().split()) print(*(i for i in range(a, b + 1) if is_prime(i)))

Эксперт Python

3600 / 1697 / 308
Регистрация: 18.01.2021
Сообщений: 3,139

Лучший ответ

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

Решение

Для 500К чисел наивный процесс может затянуться.
Кажется, что Эратосфеном придется воспользоваться

1 2 3 4 5 6 7
a, b = map( int, input().split() ) numbers = list(range(2, b + 1)) for x in numbers: if x != 0: for i in range(2 * x, b + 1, x): numbers[i - 2] = 0 print(*list(filter(lambda x: a  x  b, numbers)))

87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
Помогаю со студенческими работами здесь

Найти все простые натуральные числа, не превосходящие n, двоичная запись которых представляет собой палиндром
Программа, которая: a. запрашивает, какую из приведенных в варианте задач следует выполнить, b.

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

Найти все простые числа, меньшие данного натурального числа
Простые числа на миллион долларов Точная оценка количества простых чисел, меньших данного числа.

Найти все трехзначные простые числа
Найти все трехзначные простые числа. (Определить функцию, позволяющую распознавать простые числа.)

Найти все трехзначные простые числа
Найти все трехзначные простые числа. Добавлено через 47 минут Нужна программа в Python

Или воспользуйтесь поиском по форуму:

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

Простые числа — это натуральные числа больше единицы, которые делятся нацело только на единицу и на себя. Например, число 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

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

Как можно найти просты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 9 9 бронзовых знаков

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

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  

и не париться с абсолютным значением, но иногда приходилось считать и отрицательные простыми числами (при использовании основной теоремы арифметики), вернее не считать, а использовать отрицательные как простые при разложении

хотя для не целых чисел я бы все таки выбрасывал исключение - логически наверное более правильно это

P.S.

кстати для простого числа есть и другое определение для которого код будет вот таким коротким, без проверки на 1 и отрицательные числа:

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

Какая функция нужна для нахождения простого числа в 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 

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

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