Python prime checker неисправен с 25?

#python

Вопрос:

Итак, я относительно новичок в Python и пытаюсь определить функцию, которая будет проверять, является ли число простым или нет. Код выглядит следующим образом:

 def prime(x):
    if x < 2:
        return False
    elif x == 2:
        return True
    else:
        for i in range(3, int((x**0.5) 1)):
            if x % i == 0:
                return False
            else:
                return True

Похоже, это работает для большинства значений, однако оно терпит неудачу при определенных значениях, таких как 25, кто-нибудь может помочь мне объяснить, почему? Спасибо!

1. Ваш алгоритм неверен. Взгляните на en.wikipedia.org/wiki/Primality_test .

2. Конечно, есть более эффективные алгоритмы, но, я думаю, общая суть не так уж и плоха.

3. @RohitJ: Он действительно пытается это сделать, с int(x**0.5) 1) .

4. @RohitJ: Хотя, ему нужно только проверять простые числа, а не все натуральные числа.

5. @user667648 этот алгоритм достаточно хорош. Генерация большого списка простых чисел часто приводит к тому, что тратится больше времени, чем просто выполнение этого, особенно если это просто упражнение по изучению Python.

Ответ №1:

return покидает вашу функцию после ее достижения. Давайте посмотрим на случай 25 .

x<2 Нет, так что продолжайте.
Это x==2 нет, так что продолжайте.
x Делится на i(=3) ? Нет, поэтому перейдите к else предложению, return True оставьте функцию.

Видите проблему?

Другими словами, для достаточно больших x ваша функция эквивалентна:

 def prime_prime(x):
    if x < 2:
        return False
    elif x == 2:
        return True
    else:
        if x % 3 == 0:
            return False
        else:
            return True

Ответ №2:

Это

 else:

предложение, первое i , что оно проверяет, вернет true.

Вместо этого напишите

 else:
    for i in range(3, int((x**0.5) 1)):
        if x % i == 0:
            return False
    return True

Редактировать:
И, как указывает @mata, вам действительно нужно начинать с 2, так что это должно быть for i in range(2, int((x**0.5) 1)):

1. Может быть, хорошая идея, поскольку парень новичок в Python, обеспечить, чтобы Python воспринимал отступы . 🙂

2. Диапазон должен начинаться с 2, а не с 3. В противном случае 4, 6, 8, … считались бы простыми.

3. Вопрос @mata в том, почему он дает неправильный ответ на 25 🙂 но вы, конечно, правы. Обновлено.