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 2 3 5 7
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.
