2

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:

  1. 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?

  2. 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?

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

Brandon12
  • 23
  • 3
  • 4
    Try it with a paper and pencil, taking n=10 instead of 150. – Nate Eldredge Mar 23 '23 at 13:50
  • 3
    Each entry of P is effectively just a flag; it's only ever going to take the values 0 or 1. Think of 0 as "maybe prime" and 1 as "definitely composite". So when i=2, you will write 1 to entries 4, 6, 8, 10 which are indeed composite. When i=3 you will write 1 to entries 6 and 9 (note entry 6 was already 1, but that's okay). When i=4 you will write 1 to entry 8 (which is redundant). When i=5 you will write 1 to entry 10, also redundant. For i=6,7,8,9,10 you won't write anything. – Nate Eldredge Mar 23 '23 at 13:53
  • 3
    At the end, entries 4,6,8,9,10 have been written as 1, and the remaining entries 0,1,2,3,5,7 remain at zero. Entries 0 and 1 are not used so ignore them. That leaves 2, 3, 5, 7 which are indeed all the primes between 2 and 10. – Nate Eldredge Mar 23 '23 at 13:54
  • 2
    The values in Pi (`P[i]`) are flags — true or false, zero or non-zero. When the algorithm completes, the entries with Pi still zero mean that i is a prime number. Step 4: at the start, P2 is zero, so 2 is a prime number. Step 5: set P4, P6, P8, ... to one, indicating that 4, 6, 8 are not prime. – Jonathan Leffler Mar 23 '23 at 13:54
  • 2
    `ixj` actually means `i*j`. – Mark Ransom Mar 23 '23 at 14:02
  • @JonathanLeffler they're actually more than that, `P[i]` are a count of the number of prime factors. It's not just a boolean flag. – Mark Ransom Mar 23 '23 at 14:04
  • 1
    For step 3 it is sufficient to terminate the loop when `i * i > n`. In other words `i` should go from 2 to sqrt(n). Also, the `P` elements should all be initialized as 0 (i.e. assumed prime) except you might want to set `P[0]` and `P[1]` to 1 since 0 and 1 are not prime numbers. First time through the loop we discover `P[2] == 0` and so 2 is a prime number. Therefore all elements of `P[j]` where `j` is a multiple of `i` (2 in this case) should be set to 1 since they have `i` as a factor. Then you continuously increment `i` and repeat the check on `P[i] == 0`, etc. – Booboo Mar 23 '23 at 14:04
  • 1
    @MarkRansom That is only if you *increment* `P[j]`(i.e. setting `P[j] += 1` where `j` is a multiple of prime number `i`) instead of setting `p{j] = 1` as is being done in the OP's algorithm. – Booboo Mar 23 '23 at 14:08
  • 1
    @Booboo: I suspect Mark Ransom mentally misplaced the “Add 1” that appears in Step 6. But even if we add 1 to `p[i*j]`, that gives a count of the number of ways the number is expressible as a product, not the number of prime factors, unless the algorithm is tweaked somewhat. – Eric Postpischil Mar 23 '23 at 14:12
  • @MarkRansom Actually, if you increment `P[j]` for all `j` that are multiples of `i` where `i` is a prime number, then I believe it should give you the number of prime factors. – Booboo Mar 23 '23 at 14:34
  • @MarkRansom‚ since the algorithm says (unnecessarily) that it adds one rather than setting to one, you're right — the value in Pi is a count of the distinct prime factors for i. However, it won't record the exponents — so P9 will be 1. For large Sieves of Eratosthenes, you normally use a bitmap and set the bits to 1 when the value is composite (not prime). And you only record odd numbers. But those are refinements. – Jonathan Leffler Mar 23 '23 at 15:02
  • Sorry everybody, brain fart on my part - it does say set to 1, not increment. Shouldn't post so early in the morning I guess. – Mark Ransom Mar 23 '23 at 16:21
  • @JonathanLeffler you can optimize even further than restricting yourself to odd numbers, see https://stackoverflow.com/a/62919243/5987 – Mark Ransom Mar 23 '23 at 16:30
  • @MarkRansom — yes, and there's the [Sieve of Atikin](https://en.wikipedia.org/wiki/Sieve_of_Atkin) too. And eventually, you get into probabilistic prime detection — the [Miller-Rabin test](https://en.wikipedia.org/wiki/Prime_number#Primality_testing_versus_primality_proving) and relatives. Primality testing becomes more relevant when dealing with large numbers — numbers too big to fit in 64-bit integers. See also [Primality test](https://en.wikipedia.org/wiki/Primality_test). – Jonathan Leffler Mar 23 '23 at 17:14

1 Answers1

5

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 Pi 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 Pi 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 Pi×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 Pt to 1, denoting the fact that t is known to be non-prime (because it is the product of i and j).

Eric Postpischil
  • 195,579
  • 13
  • 168
  • 312
  • 1
    @Brandon12 Note for step 4 that this serves for not needlessly running the nested loop (`j`) for numbers that already have been determined not to be prime; e.g. with `i = 2` indices 4, 6, 8, 10, 12, ... will be set to 1; once `i` reaches 4 its multiples (8, 12, 16, ...) already have been set with `i == 2`, so you don't need to run the nested loop. You need, though, for 3 or 5 as these haven't been met yet. These will update 6 (albeit is already), 9, 12, 15, ... and 10, 15, 20, 25, (first one not yet set), 30, 35, .... – Aconcagua Mar 23 '23 at 14:05
  • 1
    @Brandon12: Possible optimisation, by the way: For each new `i` you can start the iteration with `j = i*i` (as in `for(size_t j = i*i; j <= n; j += i)` – note array size being one larger than `n`!), as for all `k < i` (current `i`) the multiples `k*i` have already been covered when `i` (historically) has been equal to `k`. This means at the same time that you can stop iterating on `i*i > n` as you can't find any further primes on `i` getting larger anyway ;) – Aconcagua Mar 23 '23 at 14:12