Thread: How booleans work in sieve of eratosthenes??

  1. #1
    Registered User
    Join Date
    Mar 2015
    Posts
    8

    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[151], 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. #2
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,302
    Quote 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.

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

    Quote 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.
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  3. #3
    Registered User
    Join Date
    Mar 2015
    Posts
    8
    Quote Originally Posted by laserlight View Post
    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[2] == 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. #4
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,302
    Quote 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.

    Quote 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[2] == 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.
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  5. #5
    Registered User
    Join Date
    Mar 2015
    Posts
    8
    Quote Originally Posted by laserlight View Post
    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[4], 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. #6
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,302
    Quote 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[4], 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[2] == 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[4] has already been set to 0, so P[4] 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.
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  7. #7
    Registered User
    Join Date
    Mar 2015
    Posts
    8

    Wink

    Quote Originally Posted by laserlight View Post
    Trace through the algorithm: when i == 2, 2 is printed since P[2] == 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[4] has already been set to 0, so P[4] 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 subscribe to a feed

Similar Threads

  1. Sieve of Eratosthenes
    By Hodor in forum C Programming
    Replies: 9
    Last Post: 11-27-2013, 02:16 AM
  2. Seg fault at about 100,000 , Sieve of Eratosthenes
    By javaeyes in forum C Programming
    Replies: 10
    Last Post: 03-12-2012, 07:38 PM
  3. Sieve of Eratosthenes
    By Eman in forum C++ Programming
    Replies: 26
    Last Post: 01-26-2011, 05:23 AM
  4. Sieve of Eratosthenes
    By darren78 in forum C++ Programming
    Replies: 0
    Last Post: 04-28-2010, 10:52 AM
  5. Sieve of Eratosthenes
    By jack_carver in forum C++ Programming
    Replies: 7
    Last Post: 04-13-2010, 10:33 PM

Tags for this Thread