Example 5: Find prime numbers.

A prime number is an integer greater than 1 that has no positive divisors other than 1 and itself. Below is an example output. Given an integer n, we want to determine all prime numbers between 1 and n (including n). Below is a program and an example output.

# 03Loops example_05_prime numbers.py

n = int(raw_input('Please input the integer n: '))

for i in range(2,n+1):
   count = 0          #Use variable count to record how many divisors the integer i has.
   for j in range(2,i):
       if(i % j ==0): 	#tests if i has divisors besides itself and the number one
           count = count + 1 	#The variable count increases
   if(count == 0): 	#After the loop, if count is still 0,  number n  is a prime number.
       print i

Please input the integer n: 10

This code contains doubly nested loops in the form of two for-loops.  The idea used is simple: consider every integer i from 2 to n and check for each i which numbers divide it without a remainder. The code is actually rather slow – if students were to run the code with n=100,000, it would take considerable time.  They will observe that the speed in which prime numbers are printed decreases quickly and they probably should know how to terminate a running program.  There exist faster ways to determine all primes less than n.    The sieve of Eratosthenes is a somewhat more efficient solution (see http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes or other on-line sources). Prime numbers are crucial to many applications, including public key cryptography, random number generation, and the effective use of hash tables.