Print series of prime numbers in python

Question

I was having issues in printing a series of prime numbers from one to hundred  I can t figure our what s wrong with my code   Here s what I wrote  it prints all the odd numbers instead of primes   for num in range 1  101       for i in range 2  num           if num   i    0              break         else              print num              break

User · Accepted Answer

You need to check all numbers from 2 to n-1 (to sqrt(n) actually, but ok, let it be n). If n is divisible by any of the numbers, it is not prime. If a number is prime, print it.

for num in range(2,101):
    prime = True
    for i in range(2,num):
        if (num%i==0):
            prime = False
    if prime:
       print (num)

You can write the same much shorter and more pythonic:

for num in range(2,101):
    if all(num%i!=0 for i in range(2,num)):
       print (num)

As I've said already, it would be better to check divisors not from 2 to n-1, but from 2 to sqrt(n):

import math
for num in range(2,101):
    if all(num%i!=0 for i in range(2,int(math.sqrt(num))+1)):
       print (num)

For small numbers like 101 it doesn't matter, but for 10**8 the difference will be really big.

You can improve it a little more by incrementing the range you check by 2, and thereby only checking odd numbers. Like so:

import math
print 2
for num in range(3,101,2):
    if all(num%i!=0 for i in range(2,int(math.sqrt(num))+1)):
       print (num)

Edited:

As in the first loop odd numbers are selected, in the second loop no need to check with even numbers, so 'i' value can be start with 3 and skipped by 2.

import math
print 2
for num in range(3,101,2):
    if all(num%i!=0 for i in range(3,int(math.sqrt(num))+1, 2)):
        print (num)

User · Answer

def prime number a       yes        for i in range  2 100           if  i  2 or i  3 or i  5 or i  7  or  i 2  0 and i 3  0 and i 5  0 and i 7  0 and i  i   float 0 5     0               yes yes  i      print  yes

User · Answer

min   int input  Enter lower range      max   int input  Enter upper range       print  The Prime numbes between  min  and  max  are     for num in range min max   1     if num   1      for i in range 2 num          if  num   i     0             break     else         print num

User · Answer

we can make a list of prime numbers using sympy library  import sympy lower int input  lower value               let it be 30 upper int input  upper value               let it be 60 l list sympy primerange lower upper 1       31 37 41 43 47 53 59  print l

User · Answer

n   int input    is prime   lambda n  all  n i    0 for i in range 2  int n   5  1    def Prime series n       for i in range 2 n           if is prime i     True              print i end                else              pass Prime series n    Here is a simplified answer using lambda function

User · Answer

You are terminating the loop too early  After you have tested all possibilities in the body of the for loop  and not breaking  then the number is prime  As one is not prime you have to start at 2   for num in xrange 2  101       for i in range 2 num           if not num   i              break     else          print num   In a faster solution you only try to divide by primes that are smaller or equal to the root of the number you are testing  This can be achieved by remembering all primes you have already found  Additionally  you only have to test odd numbers  except 2   You can put the resulting algorithm into a generator so you can use it for storing primes in a container or simply printing them out   def primes limit       if limit  gt  1          primes found     2  4           yield 2         for n in xrange 3  limit   1  2               for p  ps in primes found                  if ps  gt  n                      primes found append  n  n   n                       yield n                     break                 else                      if not n   p                          break  for i in primes 101       print i   As you can see there is no need to calculate the square root  it is faster to store the square for each prime number and compare each divisor with this number

User · Answer

First we find factor of that number  def fac n     res        for i in range 1 n 1       if n i    0  res append i    Script to check prime or not  def prime n   return fac n      1 n     Script to print all prime number upto n  def prime list n     pri list        for i in range 1 n 1       if prime i        pri list append i  return pri list

User · Answer

Print n prime numbers using python   num   input  get the value    for i in range 2 num 1       count   0     for j in range 2 i           if i j    0              count    1     if count    i-2          print i

User · Answer

min int input  min     max int input  max     for num in range min max       for x in range 2 num           if num x  0 and num  1               break         else              print num  is prime               break

User · Answer

My way of listing primes to an entry number without too much hassle is using the property that you can get any number that is not a prime with the summation of primes   Therefore  if you divide the entry number with all primes below it  and it is not evenly divisible by any of them  you know that you have a prime   Of course there are still faster ways of getting the primes  but this one already performs quite well  especially because you are not dividing the entry number by any number  but quite only the primes all the way to that number   With this code I managed on my computer to list all primes up to 100 000 in less than 4 seconds    import time as t  start   t clock    primes    2 3 5 7   for num in xrange 3 100000 2       if all num x    0 for x in primes           primes append num   print primes print t clock   - start print sum primes

User · Answer

for num in range 1 101       prime   True     for i in range 2 num 2           if  num i  0               prime   False     if prime         print num

User · Answer

How about this  Reading all the suggestions I used this   prime  2   num for num in xrange 3 m 1 2  if all num i  0 for i in range 2 int math sqrt num   1      Prime numbers up to 1000000  root nfs  pywork  time python prime py      78498       real    0m6 600s      user    0m6 532s      sys     0m0 036s

User · Answer

I was inspired by Igor and made a code block that creates a list   def prime number     for num in range 2  101       prime   True     for i in range 2  num           if  num   i    0               prime   False     if prime and num not in num list          num list append num      else          pass return num list   num list      prime number   print num list

User · Answer

The fastest  amp  best implementation of omitting primes     def PrimeRanges2 a  b       arr   range a  b 1      up   int math sqrt b     1     for d in range 2  up           arr   omit multi arr  d

User · Answer

A Python Program function module that returns the 1 st N prime numbers   def get primes count                   Return the 1st count prime integers              result          x 2     while len result  in range count           i 2         flag 0         for i in range 2 x               if x i    0                  flag  1                 break             i i 1         if flag    0              result append x          x  1     pass     return result

User · Answer

num  int input  Enter the numbner    isDivisible  False int 2  while i lt num      if num i  0     isDivisible True     print  The number    is divisible by      format num i       i   1  if isDivisible      print  The number    is not prime   format num   else      print  The number    is a prime number   format num

User · Answer

A simpler and more efficient way of solving this is storing all prime numbers found previously and checking if the next number is a multiple of any of the smaller primes   n   1000 primes    2   for i in range 3  n  2       if not any i   prime    0 for prime in primes           primes append i   print primes    Note that any is a short circuit function  in other words  it will break the loop as soon as a truthy value is found

User · Answer

a int input  enter the lower no     b int input  enter the higher no     print  Prime numbers between  a  and  b  are    for num in range a b        if num gt 1          for i in range 2 num               if  num i   0                  break         else              print num

User · Answer

Here s a simple and intuitive version of checking whether it s a prime in a RECURSIVE function      I did it as a homework assignment for an MIT class  In python it runs very fast until 1900  IF you try more than 1900  you ll get an interesting error     Would u like to check how many numbers your computer can manage    def is prime n  div 2        if div gt  n 2 0  return True      if n  div    0          return False     else          div  1         return is prime n div    The program  until   1000 for i in range until       if is prime i           print i   Of course    if you like recursive functions  this small code can be upgraded with a dictionary to seriously increase its performance  and avoid that funny error  Here s a simple Level 1 upgrade with a MEMORY integration   import datetime def is prime n  div 2       global primelist     if div gt  n 2 0  return True     if div  lt  primelist 0           div   primelist 0          for x in primelist              if x   0 or x  1  continue             if n   x    0                  return False     if n  div    0          return False     else          div  1         return is prime n div    now   datetime datetime now   print  time and date   now until   100000 primelist    for i in range until       if is prime i           primelist insert 0 i  print  There are   len primelist   prime numbers  until   until print primelist 0 100          finish   datetime datetime now   print  It took your computer   finish - now     to calculate it    Here are the resuls  where I printed the last 100 prime numbers found                  time and date  2013-10-15 13 32 11 674448           There are 9594 prime numbers  until 100000   99991  99989  99971  99961  99929  99923  99907  99901  99881  99877  99871  99859  99839  99833  99829  99823  99817  99809  99793  99787  99767  99761  99733  99721  99719  99713  99709  99707  99689  99679  99667  99661  99643  99623  99611  99607  99581  99577  99571  99563  99559  99551  99529  99527  99523  99497  99487  99469  99439  99431  99409  99401  99397  99391  99377  99371  99367  99349  99347  99317  99289  99277  99259  99257  99251  99241  99233  99223  99191  99181  99173  99149  99139  99137  99133  99131  99119  99109  99103  99089  99083  99079  99053  99041  99023  99017  99013  98999  98993  98981  98963  98953  98947  98939  98929  98927  98911  98909  98899  98897       It took your computer 0 00 40 871083  to calculate it  So It took 40 seconds for my i7 laptop to calculate it

User · Answer

Instead of trial division  a better approach  invented by the Greek mathematician Eratosthenes over two thousand years ago  is to sieve by repeatedly casting out multiples of primes    Begin by making a list of all numbers from 2 to the maximum desired prime n  Then repeatedly take the smallest uncrossed number and cross out all of its multiples  the numbers that remain uncrossed are prime    For example  consider the numbers less than 30  Initially  2 is identified as prime  then 4  6  8  10  12  14  16  18  20  22  24  26  28 and 30 are crossed out  Next 3 is identified as prime  then 6  9  12  15  18  21  24  27 and 30 are crossed out  The next prime is 5  so 10  15  20  25 and 30 are crossed out  And so on  The numbers that remain are prime  2  3  5  7  11  13  17  19  23  and 29   def primes n     sieve    True     n 1    for p in range 2  n 1       if  sieve p          print p       for i in range p  n 1  p           sieve i    False   An optimized version of the sieve handles 2 separately and sieves only odd numbers  Also  since all composites less than the square of the current prime are crossed out by smaller primes  the inner loop can start at p 2 instead of p and the outer loop can stop at the square root of n  I ll leave the optimized version for you to work on

User · Answer

Using filter function   l range 1 101  for i in range 2 10     for i in range x y   here y should be around or  lt   sqrt 101      l   filter lambda x  x  i or x i  l   print l

User · Answer

computes first n prime numbers def primes n 1       from math import sqrt     count   1     plist    2      c   3     if n  lt   0           return  Error   integer n not  gt   0      while  count  lt   n - 1        n - 1 since 2 is already in plist         pivot   int sqrt c           for i in plist              if i  gt  pivot        check for primae factors  till sqrt c                 count   1                 plist append c                  break             elif c   i    0                   break      not prime  no need to iterate anymore             else                   continue          c    2      skipping even numbers                   return plist

User · Answer

The best way to solve the above problem would be to use the  Miller Rabin Primality Test  algorithm  It uses a probabilistic approach to find if a number is prime or not  And it is by-far the most efficient algorithm I ve come across for the same   The python implementation of the same is demonstrated below   def miller rabin n  k          Implementation uses the Miller-Rabin Primality Test       The optimal number of rounds for this test is 40       See http   stackoverflow com questions 6325576 how-many-iterations-of-rabin-miller-should-i-use-for-cryptographic-safe-primes       for justification        If number is even  it s a composite number      if n    2          return True      if n   2    0          return False      r  s   0  n - 1     while s   2    0          r    1         s     2     for   in xrange k           a   random randrange 2  n - 1          x   pow a  s  n          if x    1 or x    n - 1              continue         for   in xrange r - 1               x   pow x  2  n              if x    n - 1                  break         else              return False     return True

User · Answer

Adding my own version  just to show some itertools tricks v2 7   import itertools  def Primes        primes          a   2     while True          if all itertools imap lambda p   a   p  primes                yield a             primes append a          a    1    Print the first 100 primes for    p in itertools izip xrange 100   Primes         print p

User · Answer

Here is the simplest logic for beginners to get  prime numbers   p    for n in range 2 50       for k in range 2 50           if n k   0 and n   k              break         else              for t in p                  if  n t   0                      break             else                  p append n   print p

User · Answer

Here is a different approach that trades space for faster search time   This may be fastest so   import math  def primes n       if n  lt  2          return        numbers    0   n 1      primes    2        Mark all odd numbers as maybe prime  leave evens marked composite      for i in xrange 3  n 1  2           numbers i    1      sqn   int math sqrt n         Starting with 3  look at each odd number      for i in xrange 3  len numbers   2             Skip if composite          if numbers i     0              continue           Number is prime   Would have been marked as composite if there were           any smaller prime factors already examined          primes append i          if i  gt  sqn                All remaining odd numbers not marked composite must be prime              primes extend  i for i in xrange i 2  len numbers   2                             if numbers i                break           Mark all multiples of the prime as composite   Check odd multiples          for r in xrange i i  len numbers   i 2               numbers r    0      return primes  n   1000000 p   primes n  print  Found   len p    primes  lt     n

User · Answer

I m a proponent of not assuming the best solution and testing it  Below are some modifications I did to create simple classes of examples by both  igor-chubin and  user448810  First off let me say it s all great information  thank you guys  But I have to acknowledge  user448810 for his clever solution  which turns out to be the fastest by far  of those I tested   So kudos to you  sir  In all examples I use a values of 1 million  1 000 000  as n  Please feel free to try the code out  Good luck  Method 1 as described by Igor Chubin  def primes method1 n       out   list       for num in range 1  n 1           prime   True         for i in range 2  num               if  num   i    0                   prime   False         if prime              out append num      return out  Benchmark  Over 272  seconds Method 2 as described by Igor Chubin  def primes method2 n       out   list       for num in range 1  n 1           if all num   i    0 for i in range 2  num                out append num      return out  Benchmark  73 3420000076 seconds Method 3 as described by Igor Chubin  def primes method3 n       out   list       for num in range 1  n 1           if all num   i    0 for i in range 2  int num   5     1                out append num      return out  Benchmark  11 3580000401 seconds Method 4 as described by Igor Chubin  def primes method4 n       out   list       out append 2      for num in range 3  n 1  2           if all num   i    0 for i in range 2  int num   5     1                out append num      return out  Benchmark  8 7009999752 seconds Method 5 as described by user448810  which I thought was quite clever   def primes method5 n       out   list       sieve    True     n 1      for p in range 2  n 1           if  sieve p                out append p              for i in range p  n 1  p                   sieve i    False     return out  Benchmark  1 12000012398 seconds Notes  Solution 5 listed above  as proposed by user448810  turned out to be the fastest and honestly quiet creative and clever  I love it  Thanks guys   EDIT  Oh  and by the way  I didn t feel there was any need to import the math library for the square root of a value as the equivalent is just  n   5   Otherwise I didn t edit much other then make the values get stored in and output array to be returned by the class  Also  it would probably be a bit more efficient to store the results to a file than verbose and could save a lot on memory if it was just one at a time but would cost a little bit more time due to disk writes  I think there is always room for improvement though  So hopefully the code makes sense guys   2021 EDIT  I know it s been a really long time but I was going back through my Stackoverflow after linking it to my Codewars account and saw my recently accumulated points  which which was linked to this post  Something I read in the original poster caught my eye for  user448810  so I decided to do a slight modification mentioned in the original post by filtering out odd values before appending the output array  The results was much better performance for both the optimization as well as latest version of Python 3 8 with a result of 0 723 seconds  prior code  vs 0 504 seconds using 1 000 000 for n  def primes method5 n       out   list       sieve    True     n 1      for p in range 2  n 1           if  sieve p  and sieve p  2  1               out append p              for i in range p  n 1  p                   sieve i    False     return out  Nearly five years later  I might know a bit more but I still just love Python  and it s kind of crazy to think it s been that long  The post honestly feels like it was made a short time ago and at the time I had only been using python about a year I think  And it still seems relevant  Crazy  Good times

User · Answer

Adding to the accepted answer  further optimization can be achieved by using a list to store primes and printing them after generation   import math Primes Upto   101 Primes    2  for num in range 3 Primes Upto 2       if all num i  0 for i in Primes          Primes append num  for i in Primes      print i

User · Answer

Igor Chubin s answer can be improved  When testing if X is prime  the algorithm doesn t have to check every number up to the square root of X  it only has to check the prime numbers up to the sqrt X   Thus  it can be more efficient if it refers to the list of prime numbers as it is creating it  The function below outputs a list of all primes under b  which is convenient as a list for several reasons  e g  when you want to know the number of primes  lt  b   By only checking the primes  it saves time at higher numbers  compare at around 10 000  the difference is stark     from math import sqrt def lp b      primes    2      for c in range 3 b           e   round sqrt c     1         for d in primes              if d  lt   e and c d    0                  break         else              primes extend  c       return primes

User · Answer

break ends the loop that it is currently in  So  you are only ever checking if it divisible by 2  giving you all odd numbers    for num in range 2 101       for i in range 2 num           if  num i  0               break     else          print num    that being said  there are much better ways to find primes in python than this   for num in range 2 101       if is prime num           print num   def is prime n       for i in range 2  int math sqrt n     1           if n   i    0              return False     return True

User · Answer

def function number       for j in range 2  number 1           if all j   i    0 for i in range 2  j                print j    function 13

User · Answer

f 0 sum 0 for i in range 1 101       for j in range 1 i 1           if i j  0               f f 1     if f  2           sum sum i         print i             f 0 print sum

User · Answer

This is a sample program I wrote to check if a number is prime or not    def is prime x       y 0     if x lt  1          return False     elif x    2          return True     elif x 2  0          return False     else          root   int x   5  2         for i in xrange  2 root               if x i  0                  return False                 y 1         if y  0              return True

User · Answer

n   int raw input  Enter the integer range to find prime no      p   2 while p lt n    i   p   cnt   0   while i gt 1      if p i    0          cnt  1     i- 1   if cnt    1       print   s is Prime Number  p   else       print   s is Not Prime Number  p   p  1

[python] Print series of prime numbers in python

Examples related to python

Examples related to primes

Examples related to series