Chapter 6, Problem 7E

Prime numbers can also be generated by an algorithm known as the Sieve of Eratosthenes. The algorithm for this procedure is presented here. Write a program that implements this algorithm. Have the program find all prime numbers up to n= 150. What can you say about this algorithm as compared to the ones used in the text for calculating prime numbers?

Sieve of Eratosthenes Algorithm

To Display All Prime Numbers Between 1 and n

Step 1: Define an array of integers P. Set all elements P_i to 0, 2 <= i <= n.

Step 2: Set i to 2.

Step 3: If i > n, the algorithm terminates.

Step 4: If P_i is 0, then i is prime.

Step 5: For all positive integer values of j, such that i x j≤ n, set P_ixj to 1.

Step 6: Add 1 to i and go to step 3.