Checking if a number is a prime number in Python

Question

I have written the following code  which should check if the entered number is a prime number or not  but there is an issue i couldn t get through   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     If the entered number is not a prime number  it displays  not prime   as it is supposed to  but if the number is a prime number  it doesn t display anything  Could you please help me with it

User · Answer

This is the most efficient way to see if a number is prime  if you only have a few query  If you ask a lot of numbers if they are prime try Sieve of Eratosthenes   import math  def is prime n       if n    2          return True     if n   2    0 or n  lt   1          return False      sqr   int math sqrt n     1      for divisor in range 3  sqr  2           if n   divisor    0              return False     return True

User · Answer

def prime x         check that number is greater that 1     if x  gt  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

User · Answer

def isPrime x       if x lt 2          return False     for i in range 2 x           if not x i             return False     return True        print isPrime 2     True    print isPrime 3     True    print isPrime 9     False

User · Answer

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    it worked with me just fine  D

User · Answer

Here is my take on the problem  from math import sqrt from itertools import count  islice  def is prime n       return n  gt  1 and all n   i for i in islice count 2   int sqrt n -1     This is a really simple and concise algorithm  and therefore it is not meant to be anything near the fastest or the most optimal primality check algorithm  It has a time complexity of O sqrt n    Head over here to learn more about primality tests done right and their history   Explanation I m gonna give you some insides about that almost esoteric single line of code that will check for prime numbers   First of all  using range   in Python 2 is really a bad idea  because it will create a list of numbers  which uses a lot of memory  Using xrange   is better  because it creates a generator  which only needs to memorize the initial arguments you provide  and generates every number on-the-fly  If you re using Python 3  range   has been converted to a generator by default  By the way  this is still not the best solution  trying to call xrange n  for some n such that n  gt  231-1  which is the maximum value for a C long  raises OverflowError  Therefore the best way to create a range generator is to use 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   You do not actually need to go all the way up to n if you want to check if n is a prime number  You can dramatically reduce the tests and only check from 2 to v n   square root of n   Here s an example  Let s find all the divisors of n   100  and list them in a table   2  x  50   100  4  x  25   100  5  x  20   100 10  x  10   100  lt -- sqrt 100  20  x  5    100      25  x  4    100 50  x  2    100  You will easily notice that  after the square root of n  all the divisors we find were actually already found  For example 20 was already found doing 100 5  The square root of a number is the exact mid-point where the divisors we found begin being duplicated  Therefore  to check if a number is prime  you ll only need to check from 2 to sqrt n    Why sqrt n -1 then  and not just sqrt n   That s just because the second argument provided to itertools islice   is the number of iterations to execute  islice count a   b  stops after b iterations  That s the reason why   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   The function all      is the same of the following   def all iterable        for element in iterable           if not element               return False      return True  It literally checks for all the elements in the iterable  returning False when any of them evaluates to False  which for an integer means only if it s zero   Why do we use it then  First of all  we don t need to use an additional index variable  like we would do using a loop   other than that  just for concision  there s no real need of it  but it looks way less bulky to work with only a single line of code instead of several nested lines    Extended version I m including an  quot unpacked quot  version of the is prime   function  to make it easier to understand and read  from math import sqrt from itertools import count  islice  def is prime n       if n  lt  2          return False      for number in islice count 2   int sqrt n  - 1            if n   number    0              return False      return True

User · Answer

def is prime x       n   2     if x  lt  n          return False     else              while n  lt  x             print n             if x   n    0                  return False                 break             n   n   1         else              return True

User · Answer

If a is a prime then the while x  in your code will run forever  since x will remain True   So why is that while there   I think you wanted to end the for loop when you found a factor  but didn t know how  so you added that while since it has a condition  So here is how you do it   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

User · Answer

There are many efficient ways to test primality  and this isn t one of them   but the loop you wrote can be concisely rewritten in Python   def is prime a       return all a   i for i in xrange 2  a     That is  a is prime if all numbers between 2 and a  not inclusive  give non-zero remainder when divided into a

[python] Checking if a number is a prime number in Python

Examples related to python

Examples related to primes