Проблемы с программой is_prime (x) в Python?

Question

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

Вот мой код:

def is_prime(x): 
    if x < 2: 
     print ('Please enter a number >= 2.') 
    else: 
     if x == 2 or x == 3 or x == 5: 
      return True 
     if x == 4: 
      return False 
     for num in range (2, int(x/2)): 
      if x % num == 0: 
       return False 
       break 
      else: 
       return True 

Но это возвращает Справедливо для всех нечетных чисел; а не просто первые. Я не понимаю, почему. Если бы кто-то мог указать мне в правильном направлении, это было бы очень признательно! :)

Answer 1

Ваш код проверяет только num % 2 и возвращает True или False в зависимости от результата. Таким образом, он возвращает True для всех нечетных чисел. Вы должны просто return True, если цикл не встречает return False, см. Код.

def is_prime(x): 
    if x < 2: 
     print ('Please enter a number >= 2.') 
    else: 
     if x == 2 or x == 3 or x == 5: 
      return True 
     if x == 4: 
      return False 
     for num in range (2, int(x/2)): 
      if x % num == 0: 
       return False 
     return True 


>>> is_prime(11) 
True 
>>> is_prime(9) 
False 

P.S - Вам не нужно break после return. :)

Answer 2

Этот код, который у вас есть внутри цикла, предотвращает цикл от каждого запуска более одного раза; Таким образом, вы только проверить делимости на 2. Это происходит потому, что оператор возврата немедленно прекращает все функции (таким образом, перерыв, что у вас есть также избыточный):

if x % num == 0: 
    return False 
    break 
else: 
    return True 

То, что вы, вероятно, хотите, это:

for num in range (2, int(x/2)): 
    if x % num == 0: 
      return False 
return True 

Answer 3

Проверка, является ли число премьер (эффективно) является действительно сложной задачей для выполнения, так как простые числа на самом деле не следуют какие-либо определенные закономерности: http://en.wikipedia.org/wiki/Primality_test

в коде, который является наиболее интуитивно (но неэффективный) алгоритм , вы делаете ошибку e возврата true, как только вы увидите, что число не делится на 2. Вы должны запустить весь цикл for, прежде чем определять, что ваш результат равен true. Итак, что вы должны сделать, это return false, если для некоторого num в вашем цикле вы найдете x % num == 0, но в противном случае, как только вы выйдете из цикла, просто верните true.

EDIT: Похоже, что другие люди ответили немного быстрее, чем я, так что да. Просто делайте то, что они говорят.

Answer 4

Ваша функция может быть упрощена:

def is_prime(x): 
    if x==2 or (x>2 and x%2): 
     return all(x%n for n in xrange(3, int(x**0.5)+1, 2)) 
    return False