Prime номера проверить Python

Question

Я написал это очень простую проверку простого числа:

prime = int(input()) 
if prime % prime == 0 and prime % 2 != 0 and prime % 3 != 0 or prime == 2 or prime == 3: 
    print("true") 
else: 
    print("false") 

... который, кажется, работает как-то, но я не уверен, если его правильный путь, может кто-то пожалуйста, проверьте ?

Answer 1

я не уверен, если его правильный путь

Это не так. Чтобы дать один контрпример, он считает, что 25 - простое число. Хуже того, таких контрпримеров бесконечно много.

Wikipedia Стоит прочитать для различных (правильных) методов этого.

Answer 2

Как просто, как он получает:

def isprime(n): 
    """check if integer n is a prime""" 
    # range starts with 2 and only needs to go up the squareroot of n 
    for x in xrange(2, int(n**0.5)+1): 
     if n % x == 0: 
      return False 
    return True 

Для впечатляющего генератора прайм-номера см here

Answer 3

В статье Википедии о primality может помочь вам разработать лучший алгоритм. Их много, но основные из них не так уж сложны.

• Во-первых, отойти от того, что простое число должно быть положительным целым числом больше 1. Этот инвариант следует, что если п < 2 вы можете вернуть ложные мгновенную. В вашем коде n = 0 терпит неудачу.
• В наивном подходе вы можете перейти, чтобы проверить все делители n от 1 до n. Если вы просто найдете два, то вы знаете, что это просто.
• Более интуитивный подход может заключаться в заключении, что каждое число делится на 1 и само по себе, и поэтому вы можете проверить делители только между 2 и n-1. И в тот момент, когда вы найдете делитель n, вы можете заключить, что n не является простым.
• Улучшенный подход признает, что все четные числа делятся на 2, и поэтому, если n не делится на 2, то оттуда вы можете проверять только нечетные делители.
• Наконец, вам не нужно проверять все делители до n. Достаточно проверить делитель до квадратного корня из n. Если вы не нашли дивизора, когда достигнете этого порога, вы можете сделать вывод, что n является простым.