Print series of prime numbers in python


Question

I am trying to learn Python programming, and I'm pretty new at this.

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
1
21
10/24/2017 9:59:17 PM

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
48
4/13/2018 7:50:11 AM

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.


Licensed under: CC-BY-SA with attribution
Not affiliated with: Stack Overflow
Icon