# Print series of prime numbers in python

## Print series of prime numbers in python

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 Ive 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 doesnt 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)
``````

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. Ill leave the optimized version for you to work on.

#### Print series of prime numbers in python

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