Я написал следующий код, который должен проверить, является ли введенный номер простым числом или нет, но есть проблема, с которой я не мог пройти:
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()
Если введенный номер не является простым числом, он отображает "не просто", как и предполагалось, но если число является простым числом, оно ничего не отображает. Не могли бы вы мне помочь?
Существует много эффективных способов проверки примитивности (и это не один из них). Но цикл, который вы написали, может быть кратко представлен в Python:
def is_prime(a):
return all(a % i for i in xrange(2, a))
То есть, a является простым, если все числа между 2 и a (не включительно) дают ненулевой остаток при делении на a.
На самом деле я не думаю, что в этих ответах найдено наилучшее решение, поэтому я собираюсь опубликовать свое сообщение и объяснить, почему это лучше:
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 > 231-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, если вы хотите проверить, является ли n простым числом. Вы можете значительно уменьшить тесты и проверить только от 2 до √(n) (квадратный корень от n). Вот почему:
Найдем все делители 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).
Почему sqrt(n)-1 тогда, а не только sqrt(n)? Это потому, что второй аргумент, предоставляемый объекту itertools.islice, - это количество итераций, которые нужно выполнить. islice(count(a), b) останавливается после b итераций. Вот почему:
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
Функция all(...) является тем же из следующего:
def all(iterable):
for element in iterable:
if not element:
return False
return True
он буквально проверяет все числа в iterable, возвращая False, когда число оценивается как False (что означает только, если число равно нулю). Почему мы используем его тогда? Во-первых, нам не нужно использовать дополнительную индексную переменную (например, мы будем использовать цикл), кроме этого: только для того, чтобы сделать это, реальной потребности в ней нет, но она выглядит менее громоздким для работы только с одной строкой кода вместо нескольких вложенных строк.
Я включаю "распакованную" версию функции 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
Это самый эффективный способ узнать, является ли число простым, если у вас есть только несколько запросов. Если вы задаете много чисел, если они просто попробуйте Сито Эратосфена.
import math
def is_prime(n):
if n == 2:
return True
if n % 2 == 0 or n <= 1:
return False
sqr = int(math.sqrt(n)) + 1
for divisor in range(3, sqr, 2):
if n % divisor == 0:
return False
return True
Если a является простым, тогда while x: в вашем коде будет работать вечно, так как x останется True.
Так почему же это while?
Я думаю, вы хотели закончить цикл for, когда нашли фактор, но не знали, как это сделать, поэтому вы добавили это, пока оно имеет условие. Итак, вот как вы это делаете:
def is_prime(a):
x = True
for i in range(2, a):
if a%i == 0:
x = False
break # ends the for loop
# no else block because it does nothing ...
if x:
print "prime"
else:
print "not prime"
def prime(x):
# check that number is greater that 1
if x > 1:
for i in range(2, x + 1):
# check that only x and 1 can evenly divide x
if x % i == 0 and i != x and i != 1:
return False
else:
return True
else:
return False # if number is negative
def is_prime(x):
n = 2
if x < n:
return False
else:
while n < x:
print n
if x % n == 0:
return False
break
n = n + 1
else:
return True
a = input('inter a number: ')
s = 0
if a == 1:
print a, 'is a prime'
else :
for i in range (2, a ):
if a%i == 0:
print a,' is not a prime number'
s = 'true'
break
if s == 0 : print a,' is a prime number'
он работал со мной просто отлично: D
def isPrime(x):
if x<2:
return False
for i in range(2,x):
if not x%i:
return False
return True
print isPrime (2)
Правда
print isPrime (3)
Правда
print isPrime (9)
False