Подтвердить что ты не робот

Проверка, является ли число простым числом в Python

Я написал следующий код, который должен проверить, является ли введенный номер простым числом или нет, но есть проблема, с которой я не мог пройти:

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()

Если введенный номер не является простым числом, он отображает "не просто", как и предполагалось, но если число является простым числом, оно ничего не отображает. Не могли бы вы мне помочь?

4b9b3361

ОТВЕТЫ

Ответ 1

Существует много эффективных способов проверки примитивности (и это не один из них). Но цикл, который вы написали, может быть кратко представлен в Python:

def is_prime(a):
    return all(a % i for i in xrange(2, a))

То есть, a является простым, если все числа между 2 и a (не включительно) дают ненулевой остаток при делении на a.

Ответ 2

На самом деле я не думаю, что в этих ответах найдено наилучшее решение, поэтому я собираюсь опубликовать свое сообщение и объяснить, почему это лучше:

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

Ответ 3

Это самый эффективный способ узнать, является ли число простым, если у вас есть только несколько запросов. Если вы задаете много чисел, если они просто попробуйте Сито Эратосфена.

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

Ответ 4

Если 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"

Ответ 5

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

Ответ 6

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

Ответ 7

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

Ответ 8

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