Я написал следующий код, который должен проверить, является ли введенный номер простым числом или нет, но есть проблема, с которой я не мог пройти:
def main(): n = input(«Please enter a number:») is_prime(n) def is_prime(a): x = True for i in (2, a): while x: if a%i == 0: x = False else: x = True if x: print «prime» else: print «not prime» main()
Если введенный номер не является простым числом, он отображает «не просто», как и предполагалось, но если число является простым числом, оно ничего не отображает. Не могли бы вы мне помочь?
steve 06 нояб. 2010, в 19:03
Поделиться
Примечание: for i in (2, a) цикл выполняется ровно дважды: один раз с i == 2 и один раз с i == a. Вы, вероятно, хотели использовать for i in range(2, a) .
Marius Gedminas 06 нояб. 2010, в 17:46
Поделиться:
8 ответов
Существует много эффективных способов проверки примитивности (и это не один из них). Но цикл, который вы написали, может быть кратко представлен в Python:
Как найти простые числа от 2 до 100?
def is_prime(a): return all(a % i for i in xrange(2, a))
То есть, a является простым, если все числа между 2 и a (не включительно) дают ненулевой остаток при делении на a.
user97370 07 нояб. 2010, в 13:29
Поделиться
обратите внимание, что is_prime возвращает True для 0 и 1. Однако Википедия определяет простое число как «натуральное число, большее 1, которое не имеет положительных делителей, кроме 1 и самого себя». поэтому я изменил его, чтобы return a > 1 and all(a % i for i in xrange(2, a))
Michael Osl 05 март 2014, в 21:30
просто добавьте, if x<2: return False
Cat H 11 июнь 2014, в 07:11
Я также должен добавить, что тестирование целых чисел по округленному квадрату (a) бесполезно, так как все пары факторов пересекаются в квадратном корне.
user3074620 19 июнь 2014, в 19:46
На самом деле это xrange(2, math.sqrt(a)) к множеству бесполезных сравнений: достаточно проверки в xrange(2, math.sqrt(a)) . Кроме того, xrange() вызовет OverflowError для чисел, больших чем C long, поэтому лучше использовать itertools.count и itertools.islice .
Marco Bonelli 14 янв. 2015, в 14:38
Вам может понадобиться [] вокруг части a%i
ytpillai 25 авг. 2015, в 18:26
rayryeng 17 сен. 2015, в 21:43
НЕ ИСПОЛЬЗУЙТЕ ЭТУ ФУНКЦИЮ! Вот причины. 1) Возвращает true, если a == 1, но 1 не считается простым числом. 2) Он проверяет, является ли число простым, пока a — 1, но приличный программист знает, что это необходимо только до sqrt (a). 3) Он не пропускает четные числа: кроме 2, все простые числа нечетные.
4) Он не показывает алгоритмическое мышление, лежащее в основе того, как найти простое число, потому что он использует товары Python. 5) xrange не существует в Python 3, поэтому некоторые люди не смогут его запустить.
nbro 18 янв. 2016, в 19:36
Показать ещё 5 комментариев
На самом деле я не думаю, что в этих ответах найдено наилучшее решение, поэтому я собираюсь опубликовать свое сообщение и объяснить, почему это лучше:
7.9 Простые числа. «Поколение Python»: курс для начинающих. Курс Stepik
from math import sqrt; from itertools import count, islice def isPrime(n): return n > 1 and all(n%i for i in islice(count(2), int(sqrt(n)-1)))
Примечание: требуется проверка n > 1 , так как 1 не является простым числом, и поэтому равно нулю и любой отрицательное число.
Описание
Я собираюсь дать вам немного информации об этой почти эзотерической одиночной строке кода, которая будет проверять простые числа:
-
Прежде всего, использование range() — действительно плохая идея, потому что он создаст список чисел, в котором используется много памяти. Использование xrange() лучше, потому что оно создает generator , который не использует память для работы, но генерирует каждое число «на лету». Кстати, это не лучшее решение: попытка вызвать xrange(n) для некоторого n таким образом, что n > 2 31 -1 (что является максимальным значением для C long) вызывает OverflowError . Поэтому лучший способ создать диапазон generator — использовать itertools :
xrange(2147483647+1) # OverflowError from itertools import count, islice count(1) # Count from 1 to infinity with step=+1 islice(count(1), 2147483648) # Count from 1 to 2^31 with step=+1 islice(count(1, 3), 2147483648) # Count from 1 to 3*2^31 with step=+3
-
Найдем все делители n = 100 и перечислим их в таблице:
2 x 50 = 100 4 x 25 = 100 5 x 20 = 100 10 x 10 = 100 -> Square root of 100 20 x 5 = 100 25 x 4 = 100 50 x 2 = 100
Вы легко заметите, что после квадратного корня из n все найденные делители на самом деле уже найдены. Например, 20 уже был найден с помощью 100/5 . Квадратный корень из числа — это точная средняя линия, где найденные делители начинают дублироваться. Поэтому , чтобы проверить, является ли число простым, вам нужно всего лишь проверить от 2 до sqrt(n) .
for number in islice(count(10), 2): print number, # Will print: 10 11 for number in islice(count(1, 3), 10): print number, # Will print: 1 4 7 10 13 16 19 22 25 28
def all(iterable): for element in iterable: if not element: return False return True
Расширенная версия
Я включаю «распакованную» версию функции isPrime() , чтобы ее было легче понять и прочитать:
from math import sqrt from itertools import count, islice def isPrime(n): if n < 2: return False for number in islice(count(2), int(sqrt(n)-1)): if not n%number: return False return True
Источник: overcoder.net
Python. Как написать функцию, возвращающую список простых чисел .
Функция is_prime(n) проверяет, является ли число n простым. Она возвращает True, если число простое, и False в противном случае. Для этого она проверяет делится ли число на другие числа от 2 до корня из числа.
Функция fun(m, n) использует функцию is_prime() для фильтрации чисел в интервале от m до n включительно, оставляя только простые числа. Она использует списочное включение, чтобы создать новый список, который содержит только простые числа из интервала от m до n включительно в порядке возрастания.
В данном примере при вызове функции fun(20,30) создается список из простых чисел [23, 29] в интервале от 20 до 30 включительно.
Источник: www.bolshoyvopros.ru
Как проверить, является ли число простым или нет с помощью Python?
Принцип, используемый в следующем решении этой проблемы, состоит в том, чтобы разделить данное число со всеми из 3 его квадратного корня, квадратный корень числа является наибольшим возможным фактором, за которым нет необходимости проверять, делится ли оно на любое другое число, чтобы решить, что оно является простое число.
Функция возвращает ложь для всех чисел, кратных 2 и меньшим 2. Для других возвращаемое значение всех) функция будет ложной, если она делится на любое число вплоть до ее квадратного корня, и истинной, если она не делится на любое число.
Пример
def is_prime(a): if a < 2: return False elif a!=2 and a % 2 == 0: return False else: return all (a % i for i in range(3, int(a**0.5)+1) ) num=int(input(‘enter a number’)) if is_prime(num)==True: print («<>is a prime number».format(num)) else: print («<> is not a prime number».format(num))
Вывод
Пример запуска вышеуказанной программы —
enter a number24 24 is not a prime number enter a number47 47 is a prime number
Источник: pythononline.ru