How to implement Sieve of Eratosthenes Algorithm in C?

In my book, Programming in C (fourth edition) by Stephen G. Kochan, I have a task to implement the Sieve of Eratosthenes algorithm as follows:

Display All Prime Numbers Between 1 and n = 150

Step 1: Define an array of integers P. Set all elements Pi to 0,
```
     2 <= i <= n.
```
Step 2: Set i to 2.
Step 3: If i > n, the algorithm terminates.
Step 4: If Pi is 0, then i is prime.
Step 5: For all positive integer values of j, such that i x j ≤ n,

     set <sub>Pixj</sub> to 1.
 Step 6: Add 1 to i and go to step 3.

I understand the broad concept but have a hard time understanding the steps in the algorithm and the purpose of each one.

Questions:

In step 1, what is the purpose of setting all elements p[i] to 0? Wouldn't the array elements need to be from 0 to 150 starting out?
In step 4, does it mean that the multiples of i get the value 0 and if any other value than zero will be prime? Essentialy, it would convert all multiples of i to 0 (composite) and leave all prime numbers?
Step 5 has me confused all together, I'm not sure how to form a coherent question on this. What does a subscript like this mean _Pixj? Also, the logic of step 4 does not make sense, I need something in more laymens terms if possible. (just a hint would be fine so I can get it myself)

FYI I am a beginner in learning the basics of computer science and programming so less cryptic responses will be appreciated! This exercise above is from Chapter 6: Arrays. Thank you!

I have not attempted in code yet, I need to understand the algorithmic steps first.

Solution

In step 1, what is the purpose of setting all elements p[i] to 0? Wouldn't the array elements need to be from 0 to 150 starting out?

The array P is used to record whether an integer is known to be non-prime. Each element P_i is initialized to zero to denote the fact that, initially, the algorithm does not know whether i is non-prime.

In step 4, does it mean that the multiples of i get the value 0 and if any other value than zero will be prime? [Essentially], it would convert all multiples of i to 0 (composite) and leave all prime numbers?

Step 4 is poorly stated. When step 4 is reached in the algorithm, sufficient work has been performed that, if P_i is zero, then i must be prime. In step 4, the algorithm is intended to report this fact by some means, such as writing i to standard output.

Step 5 has me confused all together, I'm not sure how to form a coherent question on this. What does a subscript like this mean Pixj? Also, the logic of step 4 does not make sense, I need something in more laymens terms if possible. (just a hint would be fine so I can get it myself)

“Pixj” means P_i×j. In step 5, the algorithm has an i and iterates through a loop on j. In each iteration of that loop, the code should calculate the product t = i×j and set P_t to 1, denoting the fact that t is known to be non-prime (because it is the product of i and j).