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

Answer 1

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.

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!!

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.

---

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

Answer 2

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)

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)

Answer 3

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 product 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)

Answer 4

as one line comprehension list solution:

>>> [num for num in range(2, 101) if all(num % i != 0 for i in range(2, num))]
[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]

which 101 represent the maximum range value between 2 and 100 of list

1 can only be divided by one number, 1 itself, so with this definition 1 is not a prime number. The primary number must have only two positive factors 1 and itself.

Answer 5

for i in range(1, 100):
  for j in range(2, i):
    if i % j == 0:
      break 
  else:
    print(i)

Answer 6

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)

Answer 7

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.

Answer 8

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)

Answer 9

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.

Answer 10

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)

Answer 11

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)

Answer 12

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>1:
        for i in range(2,num):
            if (num%i)==0:
                break
        else:
            print(num)

Answer 13

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

Answer 14

num= int(input("Enter the numbner"))
isDivisible= False
int=2

while i<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))

Answer 15

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

Answer 16

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)

Answer 17

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

Answer 18

Here is a different approach that trades space for faster search time. This may be fastest so.

import math

def primes(n):
    if n < 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 > 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 <=", n

Answer 19

The fastest & 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)

Answer 20

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

Answer 21

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

Answer 22

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

Answer 23

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

Answer 24

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

Answer 25

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 <= sqrt(101)
    l = filter(lambda x: x==i or x%i, l)

print l

Answer 26

n = int(raw_input('Enter the integer range to find prime no :'))
p = 2
while p<n:
  i = p
  cnt = 0
  while i>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

Answer 27

This is a sample program I wrote to check if a number is prime or not.

def is_prime(x):
    y=0
    if x<=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

Answer 28

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 > 1:
        primes_found = [(2, 4)]
        yield 2
        for n in xrange(3, limit + 1, 2):
            for p, ps in primes_found:
                if ps > 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.

Answer 29

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

Answer 30

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