Simple prime number generator in Python

Question

Could someone please tell me what I m doing wrong with this code  It is just printing  count  anyway   I just want a very simple prime generator  nothing fancy     import math  def main        count   3     one   1     while one    1          for x in range 2  int math sqrt count    1                if count   x    0                   continue             if count   x    0                  print count          count    1

User · Answer

print  x for x in range 2 100  if not  t for t in range 2 x  if not x t

User · Answer

python 3  generate prime number   import math  i   2 while True      for x in range 2  int math sqrt i    1            if i x  0              break     else          print i      i    1

User · Answer

Here s a simple  Python 2 6 2  solution    which is in-line with the OP s original request  now six-months old   and should be a perfectly acceptable solution in any  programming 101  course    Hence this post   import math  def isPrime n       for i in range 2  int math sqrt n  1            if n   i    0               return False      return n gt 1   print 2 for n in range 3  50       if isPrime n           print n   This simple  brute force  method is  fast enough  for numbers upto about about 16 000 on modern PC s  took about 8 seconds on my 2GHz box    Obviously  this could be done much more efficiently  by not recalculating the primeness of every even number  or every multiple of 3  5  7  etc for every single number    See the Sieve of Eratosthenes  see eliben s implementation above   or even the Sieve of Atkin if you re feeling particularly brave and or crazy   Caveat Emptor  I m a python noob  Please don t take anything I say as gospel

User · Answer

Similar to user107745  but using  all  instead of double negation  a little bit more readable  but I think same performance    import math  x for x in xrange 2 10000  if all x t for t in xrange 2 int math sqrt x   1      Basically it iterates over the x in range of  2  100  and picking only those that do not have mod    0 for all t in range 2 x   Another way is probably just populating the prime numbers as we go   primes   set   def isPrime x     if x in primes      return x   for i in primes      if not x   i        return None   else      primes add x      return x  filter isPrime  range 2 10000

User · Answer

SymPy is a Python library for symbolic mathematics  It provides several functions to generate prime numbers   isprime n                 Test if n is a prime number  True  or not  False    primerange a  b           Generate a list of all prime numbers in the range  a  b   randprime a  b            Return a random prime number in the range  a  b   primepi n                 Return the number of prime numbers less than or equal to n   prime nth                 Return the nth prime  with the primes indexed as prime 1    2  The nth prime is approximately n log n  and can never be larger than 2  n  prevprime n  ith 1        Return the largest prime smaller than n nextprime n               Return the ith prime greater than n  sieve primerange a  b     Generate all prime numbers in the range  a  b   implemented as a dynamically growing sieve of Eratosthenes     Here are some examples    gt  gt  gt  import sympy  gt  gt  gt    gt  gt  gt  sympy isprime 5  True  gt  gt  gt  list sympy primerange 0  100    2  3  5  7  11  13  17  19  23  29  31  37  41  43  47  53  59  61  67  71  73  79  83  89  97   gt  gt  gt  sympy randprime 0  100  83  gt  gt  gt  sympy randprime 0  100  41  gt  gt  gt  sympy prime 3  5  gt  gt  gt  sympy prevprime 50  47  gt  gt  gt  sympy nextprime 50  53  gt  gt  gt  list sympy sieve primerange 0  100    2  3  5  7  11  13  17  19  23  29  31  37  41  43  47  53  59  61  67  71  73  79  83  89  97

User · Answer

Just studied the topic  look for the examples in the thread and try to make my version   from collections import defaultdict   from pprint import pprint  import re   def gen primes limit None          Sieve of Eratosthenes        not prime   defaultdict list      num   2     while limit is None or num  lt   limit          if num in not prime              for prime in not prime num                   not prime prime   num  append prime              del not prime num          else     Prime number             yield num             not prime num   num     num            It s amazing to debug it this way            pprint  num  dict not prime    width 1            input           num    1   def is prime num          Check if number is prime based on Sieve of Eratosthenes        return num  gt  1 and list gen primes limit num   pop      num   def oneliner is prime num          Simple check if number is prime        return num  gt  1 and not any  num   x    0 for x in range 2  num      def regex is prime num       return re compile r  1     11   1     match  1    num  is None   def simple is prime num          Simple check if number is prime     More efficient than oneliner is prime as it breaks the loop             for x in range 2  num           if num   x    0              return False     return num  gt  1   def simple gen primes limit None          Prime number generator based on simple gen        num   2     while limit is None or num  lt   limit          if simple is prime num               yield num         num    1   if   name         main         less1000primes   list gen primes limit 1000       assert less1000primes    list simple gen primes limit 1000       for num in range 1000           assert                num in less1000primes                 is prime num                 oneliner is prime num                 regex is prime num                 simple is prime num                print  Primes less than 1000        print less1000primes       from timeit import timeit      print   nTimeit        print           gen primes            timeit               list gen primes limit 1000                 setup  from   main   import gen primes               number 1000                       print           simple gen primes            timeit               list simple gen primes limit 1000                 setup  from   main   import simple gen primes               number 1000                       print           is prime            timeit                is prime num  for num in range 2  1000                 setup  from   main   import is prime               number 100                       print           oneliner is prime            timeit                oneliner is prime num  for num in range 2  1000                 setup  from   main   import oneliner is prime               number 100                       print           regex is prime            timeit                regex is prime num  for num in range 2  1000                 setup  from   main   import regex is prime               number 100                       print           simple is prime            timeit                simple is prime num  for num in range 2  1000                 setup  from   main   import simple is prime               number 100                     The result of running this code show interesting results     python prime time py Primes less than 1000   2  3  5  7  11  13  17  19  23  29  31  37  41  43  47  53  59  61  67  71  73  79  83  89  97  101  103  107  109  113  127  131  137  139  149  151  157  163  167  173  179  181  191  193  197  199  211  223  227  229  233  239  241  251  257  263  269  271  277  281  283  293  307  311  313  317  331  337  347  349  353  359  367  373  379  383  389  397  401  409  419  421  431  433  439  443  449  457  461  463  467  479  487  491  499  503  509  521  523  541  547  557  563  569  571  577  587  593  599  601  607  613  617  619  631  641  643  647  653  659  661  673  677  683  691  701  709  719  727  733  739  743  751  757  761  769  773  787  797  809  811  821  823  827  829  839  853  857  859  863  877  881  883  887  907  911  919  929  937  941  947  953  967  971  977  983  991  997   Timeit  gen primes  0 6738066330144648 simple gen primes  4 738092333020177 is prime  31 83770858097705 oneliner is prime  3 3708438930043485 regex is prime  8 692703998007346 simple is prime  0 4686249239894096   So I can see that we have right answers for different questions here  for a prime number generator gen primes looks like the right answer  but for a prime number check  the simple is prime function is better suited   This works  but I am always open to better ways to make is prime function

User · Answer

Here is a numpy version of Sieve of Eratosthenes having both okay complexity  lower than sorting an array of length n  and vectorization   import numpy as np  def generate primes n       is prime   np ones n 1 dtype bool      is prime 0 2    False     for i in range int n  0 5  1           if is prime i               is prime i 2  i  False     return np where is prime  0    Timings    import time     for i in range 2 10       timer  time time       generate primes 10  i      print  n   10   i   time     round time time  -timer 6     gt  gt  n   10  2  time   5 6e-05  gt  gt  n   10  3  time   6 4e-05  gt  gt  n   10  4  time   0 000114  gt  gt  n   10  5  time   0 000593  gt  gt  n   10  6  time   0 00467  gt  gt  n   10  7  time   0 177758  gt  gt  n   10  8  time   1 701312  gt  gt  n   10  9  time   19 322478

User · Answer

This is my implementation  Im sure there is a more efficient way  but seems to work  Basic flag use   def genPrime        num   1     prime   False     while True            Loop through all numbers up to num         for i in range 2  num 1                 Check if num has remainder after the modulo of any previous numbers             if num   i    0                  prime   False                   Num is only prime if no remainder and i is num                 if i    num                      prime   True                 break          if prime              yield num             num    1         else              num    1  prime   genPrime   for   in range 100       print next prime

User · Answer

re is powerful   import re   def isprime n       return re compile r  1     11   1     match  1    n  is None  print  x for x in range 100  if isprime x               Output               2  3  5  7  11  13  17  19  23  29  31  37  41  43  47  53  59  61  67  71  73  79  83  89  97

User · Answer

You need to make sure that all possible divisors don t evenly divide the number you re checking   In this case you ll print the number you re checking any time just one of the  possible divisors doesn t evenly divide the number   Also you don t want to use a continue statement because a continue will just cause it to check the next possible divisor when you ve already found out that the number is not a prime

User · Answer

For me  the below solution looks simple and easy to follow    import math  def is prime num        if num  lt  2          return False      for i in range 2  int math sqrt num    1            if num   i    0              return False  return True

User · Answer

import time  maxnum input  You want the prime number of 1 through        n 2 prime    start time time    while n lt  maxnum       d 2 0     pr True     cntr 0      while d lt n   5           if n d  0              pr False         else              break         d d 1      if cntr  0           prime append n           print n      n n 1  print  Total time   time time  -start

User · Answer

How about this if you want to compute the prime directly   def oprime n   counter   0 b   1 if n    1      print 2 while counter  lt  n-1      b   b   2     for a in range 2 b           if b   a    0              break     else          counter   counter   1         if counter    n-1              print b

User · Answer

The continue statement looks wrong  You want to start at 2 because 2 is the first prime number  You can write  while True   to get an infinite loop

User · Answer

There are some problems   Why do you print out count when it didn t divide by x  It doesn t mean it s prime  it means only that this particular x doesn t divide it continue moves to the next loop iteration - but you really want to stop it using break  Here s your code with a few fixes  it prints out only primes  import math  def main        count   3           while True          isprime   True                   for x in range 2  int math sqrt count    1                if count   x    0                   isprime   False                 break                   if isprime              print count                   count    1  For much more efficient prime generation  see the Sieve of Eratosthenes  as others have suggested  Here s a nice  optimized implementation with many comments    Sieve of Eratosthenes   Code by David Eppstein  UC Irvine  28 Feb 2002   http   code activestate com recipes 117119   def gen primes         quot  quot  quot  Generate an infinite sequence of prime numbers       quot  quot  quot        Maps composites to primes witnessing their compositeness        This is memory efficient  as the sieve is not  quot run forward quot        indefinitely  but only as long as required by the current       number being tested            D                  The running integer that s checked for primeness     q   2           while True          if q not in D                q is a new prime                Yield it and mark its first multiple that isn t               already marked in previous iterations                            yield q             D q   q     q          else                q is composite  D q  is the list of primes that               divide it  Since we ve reached q  we no longer               need it in the map  but we ll mark the next                multiples of its witnesses to prepare for larger               numbers                            for p in D q                   D setdefault p   q      append p              del D q                    q    1  Note that it returns a generator

User · Answer

def primes n     simple sieve of multiples     odds   range 3  n 1  2     sieve   set sum  list range q q  n 1  q q   for q in odds           return  2     p for p in odds if p not in sieve    gt  gt  gt  primes 50   2  3  5  7  11  13  17  19  23  29  31  37  41  43  47   To test if a number is prime   gt  gt  gt  541 in primes 541  True  gt  gt  gt  543 in primes 543  False

User · Answer

This seems homework-y  so I ll give a hint rather than a detailed explanation  Correct me if I ve assumed wrong   You re doing fine as far as bailing out when you see an even divisor    But you re printing  count  as soon as you see even one number that doesn t divide into it  2  for instance  does not divide evenly into 9   But that doesn t make 9 a prime  You might want to keep going until you re sure no number in the range matches    as others have replied  a Sieve is a much more efficient way to go    just trying to help you understand why this specific code isn t doing what you want

User · Answer

def check prime x       if  x  lt  2           return 0     elif  x    2           return 1     t   range x      for i in t 2           if  x   i    0               return 0     return 1

User · Answer

Using generator   def primes num       if 2  lt   num          yield 2     for i in range 3  num   1  2           if all i   x    0 for x in range 3  int math sqrt i    1                 yield i   Usage   for i in primes 10       print i       2  3  5  7

User · Answer

To my opinion it is always best to take the functional approach   So I create a function first to find out if the number is prime or not then use it in loop or other place as necessary   def isprime n         for x in range 2 n           if n x    0              return False     return True   Then run a simple list comprehension or generator expression to get your list of prime    x for x in range 1 100  if isprime x

User · Answer

You can create a list of primes using list comprehensions in a fairly elegant manner  Taken from here    gt  gt  gt  noprimes    j for i in range 2  8  for j in range i 2  50  i    gt  gt  gt  primes    x for x in range 2  50  if x not in noprimes   gt  gt  gt  print primes  gt  gt  gt   2  3  5  7  11  13  17  19  23  29  31  37  41  43  47

User · Answer

If you wanted to find all the primes in a range you could do this     def is prime num      Returns True if the number is prime else False     if num    0 or num    1      return False for x in range 2  num       if num   x    0          return False else      return True num   0 itr   0 tot      while itr  lt   100      itr   itr   1     num   num   1     if is prime num     True          print num          tot   tot         str num  print tot    Just add while its  lt   and your number for the range  OUTPUT  2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 101

User · Answer

def genPrimes        primes          primes generated so far     last   1        last number tried     while True          last    1         for p in primes              if last   p    0                  break         else              primes append last              yield last

User · Answer

Here is what I have   def is prime num       if num  lt  2          return False     elif num  lt  4        return True     elif not num   2    return False     elif num  lt  9        return True     elif not num   3    return False     else          for n in range 5  int math sqrt num    1   6               if not num   n                  return False             elif not num    n   2                   return False      return True   It s pretty fast for large numbers  as it only checks against already prime numbers for divisors of a number   Now if you want to generate a list of primes  you can do     primes up to  max  def primes max max       yield 2     for n in range 3  max  2           if is prime n               yield n    the first  count  primes def primes count count       counter   0     num   3      yield 2      while counter  lt  count          if is prime num               yield num             counter    1         num    2   using generators here might be desired for efficiency   And just for reference  instead of saying   one   1 while one    1        do stuff   you can simply say   while 1       do stuff

User · Answer

def is prime num          Returns True if the number is prime     else False         if num    0 or num    1          return False     for x in range 2  num           if num   x    0              return False     else          return True   gt  gt  filter is prime  range 1  20      2  3  5  7  11  13  17  19    We will get all the prime numbers upto 20 in a list  I could have used Sieve of Eratosthenes but you said you want something very simple

User · Answer

Another simple example  with a simple optimization of only considering odd numbers  Everything done with lazy streams  python generators    Usage  primes   list create prime iterator 1  30    import math import itertools  def create prime iterator rfrom  rto          Create iterator of prime numbers in range  rfrom  rto         prefix    2  if rfrom  lt  3 and rto  gt  1 else      include 2 if it is in range separately as it is a  weird  case of even prime     odd rfrom   3 if rfrom  lt  3 else make odd rfrom    make rfrom an odd number so that  we can skip all even nubers when searching for primes  also skip 1 as a non prime odd number      odd numbers    num for num in xrange odd rfrom  rto   1  2       prime generator    num for num in odd numbers if not has odd divisor num       return itertools chain prefix  prime generator   def has odd divisor num          Test whether number is evenly divisable by odd divisor         maxDivisor   int math sqrt num       for divisor in xrange 3  maxDivisor   1  2           if num   divisor    0              return True     return False  def make odd number          Make number odd by adding one to it if it was even  otherwise return it unchanged        return number   1

[python] Simple prime number generator in Python

Examples related to python

Examples related to primes