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

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) 

Answer 2

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.