# Thread: How booleans work in sieve of eratosthenes??

1. ## How booleans work in sieve of eratosthenes?? I understand the sieve of eratosthenes on paper but in c code I find it hard to get the logic of using booleans like 1 and 0 to filter primes. In the code below, the algorithm for which is detailed in kochan's programming in c, I find it hard to break down the code and find how booleans help?

Code:
```#include<stdio.h>
int main (void)
{
int  P, i, j;// Also why is p initialized 1 more than n?
int  n = 150;

for (i = 2; i <= n; ++i)
P[i] = 1;

i = 2;

while (i <= n) {
if (P[i] == 1)// how does this identify a prime?
printf("%i  ", i);

j = 1;

while (i * j <= n) {
P[i * j] = 0;
++j; //why are non- primes accumulated?
}```
Can anyone please help me analyze what's going on here. Also any suggestions on the code's optimization will be greatly useful for me in future. 2. Originally Posted by avidrutham
Also why is p initialized 1 more than n?
Observe that the loop condition is i <= n. Therefore, on the last iteration, P[n] will be accessed. If P had exactly n elements, then there would be an out of bounds access. Originally Posted by avidrutham
how does this identify a prime?
Recall that the idea behind this sieve is to "cross out" the positions of composites, which in this context means setting them to 0. So, if we reach a position i such that the element at that position has a value of 1, it must be prime since it was not "crossed out" on a previous iteration. Originally Posted by avidrutham
why are non- primes accumulated?
The idea is to "cross out" the other composites that are multiples of that number, as you should have already done on paper. 3. Originally Posted by laserlight Observe that the loop condition is i <= n. Therefore, on the last iteration, P[n] will be accessed. If P had exactly n elements, then there would be an out of bounds access.

Recall that the idea behind this sieve is to "cross out" the positions of composites, which in this context means setting them to 0. So, if we reach a position i such that the element at that position has a value of 1, it must be prime since it was not "crossed out" on a previous iteration.

The idea is to "cross out" the other composites that are multiples of that number, as you should have already done on paper.
Thank you for the response and please bear with me a little more. I observe that the code initializes all elements in p to 1 in the beginning. At this rate all no.s could have been printed as primes, as the first condition checked in the next loop is p == 1. In my eyes the code translates as p == 1. This I do not understand. After all, in the code we do not explicitly try to find multiples like in the original technique by eratosthenes, so how are booleans at work here? 4. Originally Posted by avidrutham
I observe that the code initializes all elements in p to 1 in the beginning.
True, at least other than the elements at indices 0 and 1 since 0 and 1 are typically not regarded as prime and so were skipped entirely. Originally Posted by avidrutham
At this rate all no.s could have been printed as primes, as the first condition checked in the next loop is p == 1. In my eyes the code translates as p == 1. This I do not understand. After all, in the code we do not explicitly try to find multiples like in the original technique by eratosthenes, so how are booleans at work here?
The code does "try to find" multiples. That is what the inner loop is about, and notice that P[i * j] is set to 0 in the inner loop. 5. Originally Posted by laserlight True, at least other than the elements at indices 0 and 1 since 0 and 1 are typically not regarded as prime and so were skipped entirely.

The code does "try to find" multiples. That is what the inner loop is about, and notice that P[i * j] is set to 0 in the inner loop.
Actually, what confuses me is that the print command is given before the test for multiples is done. So when we reach say p, which is set to 1 in the earlier loop, the test done on that is after the print, so shouldn't 4 get printed. Of course, it doesn't, but that's what I'm trying to solve for myself.
Also how does some thing like p[4 * 1] == 0 sort the non - primes. 6. Originally Posted by avidrutham
Actually, what confuses me is that the print command is given before the test for multiples is done. So when we reach say p, which is set to 1 in the earlier loop, the test done on that is after the print, so shouldn't 4 get printed. Of course, it doesn't, but that's what I'm trying to solve for myself.
Also how does some thing like p[4 * 1] == 0 sort the non - primes.
Trace through the algorithm: when i == 2, 2 is printed since P == 1. Then in the inner loop the elements at index 4, 6, 8, etc are set to 0. By the time you get to i == 4, P has already been set to 0, so P is not printed.

EDIT:
Uh, only now did I notice that the code that you posted is incomplete, but presumably i is incremented somewhere at the end of the outer loop body. 7. ##  Originally Posted by laserlight Trace through the algorithm: when i == 2, 2 is printed since P == 1. Then in the inner loop the elements at index 4, 6, 8, etc are set to 0. By the time you get to i == 4, P has already been set to 0, so P is not printed.

EDIT:
Uh, only now did I notice that the code that you posted is incomplete, but presumably i is incremented somewhere at the end of the outer loop body.
Hi, laserlight, I know this is coming late but I finally figured how the second loop is working..Thanks for all your ideas. Also the code I pasted was incomplete. It does have ++i in the end. Popular pages Recent additions #### Tags for this Thread

beginner programmer, logic programming 