3 Replies - 309 Views - Last Post: 13 May 2013 - 05:53 AM Rate Topic: -----

#1 pulp_fiction  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 36
  • Joined: 03-February 13

Sieve of Eratosthenes:My Failed Attempt

Posted 13 May 2013 - 04:40 AM

There was this question about implementing SIEVE OF ERATOSTHENES in C using pointers. You are given an array of 1000
elements (integers).Store them all with 1(TRUE) at the beginning.Now,follow SOE to cross out multiples starting with
multiples of 2.Now it is emphasized to take 2 pointers one for storing the address of first element of array and the second for last element.
CONSTRAINT:use only pointer arithmetic.Use of subscript to make it easy is not allowed.Use just 0 & 999 subscript to acquire the addresses of first and last element.
The upper limit of SOE is 1000.
At last I have displayed all the prime numbers(not crossed out).

Problem:Had I seen an error or garbage output.I would still be like(Fine-What now?).But here I am getting a DON'T SEND
(probably some crash)error.Can you tell me the cause of this error.I have seen this before too.I have always wondered -why this out of all possibilities.

Here is the code:
#include<stdio.h>

void sieve_of_eratosthenes(void);
int main()
{
    sieve_of_eratosthenes();
    return 0;
}

void sieve_of_eratosthenes(void)
{
    int record[1000],i,n;
    int *p1=&record[0],*p2=&record[999];
    //Initialization
    while(p1<=p2)
    {
        *(p1++)=1;       //All have been assumed as true
    }
    p1=&record[0];
    p1+=2;
    for(i=2;i<=1000;)
    {
        if(*p1==0)
        {
            i++;
            continue;
        }
        n=i;
        while(p1<=p2)
        {
            p1+=n;
            *p1=0;
        }
        p1=&record[0]+ (++i);
    }
    p1=&record[2];
    for(i=2;i<=1000;i++)
    {
        if(*p1==1)
        {
            printf("%d\t",i);
        }
        if(i%4==0)
            printf("\n");
    }
}


If you need any other info. ,let me know.

Is This A Good Question/Topic? 0
  • +

Replies To: Sieve of Eratosthenes:My Failed Attempt

#2 Zereo  Icon User is offline

  • D.I.C Head
  • member icon

Reputation: 43
  • View blog
  • Posts: 108
  • Joined: 08-November 12

Re: Sieve of Eratosthenes:My Failed Attempt

Posted 13 May 2013 - 04:55 AM

You are trying to access a element that is outside of you arrays bounds most likely. I would suggest running your code through a debuggers and seeing exactly where you get the run time crash. Once you see what line it crashes on you will find your problem.

Specifically look at this part in your code

while(p1<=p2)
{
   p1+=n;
   *p1=0;
}


What will n equal when it first hits this loop? What about the second time? And then so on? It will then keep running through that while loop moving lets say 3 elements forward. So lets say we are at element number 999 which is what p2 points to. It still runs the while loop because 999 is less then or equal to 999. So we enter the loop and we move forward 3 elements (Because that is what n equals), so now p1 will equal element 1002 which isn't in our array! We then try to assign 0 to that element and get a run time error. That is somewhere along the lines of what is happening.

This might not be the only problem in the program so I would suggest using your debugger. To see how your program runs and what the values are.

Debugging is a very useful skill to learn. I would recommend checking out some of our tutorials on it on this forum. A few hours learning this very important skill will says you hundreds of hours of pain in the future.

This post has been edited by Zereo: 13 May 2013 - 07:44 AM

Was This Post Helpful? 0
  • +
  • -

#3 Mallstrop  Icon User is offline

  • New D.I.C Head

Reputation: 6
  • View blog
  • Posts: 47
  • Joined: 19-June 08

Re: Sieve of Eratosthenes:My Failed Attempt

Posted 13 May 2013 - 05:41 AM

It's just a guess, I've not tested it.

I'd suggest looking at line 17, I think you increment p1 and then assign too it. The loop condition means this can go beyond the end of the array.

My advice would always be not to try and do any more than is required in any one line of code, I see it all the time at work, someone trying to be too smart, trying to minimize the number of lines of code and creating unexpected side effects.

Replace
*(p1++)=1; 

with
*p1 = 1;
p1++;

This post has been edited by Mallstrop: 13 May 2013 - 05:49 AM

Was This Post Helpful? 0
  • +
  • -

#4 Zereo  Icon User is offline

  • D.I.C Head
  • member icon

Reputation: 43
  • View blog
  • Posts: 108
  • Joined: 08-November 12

Re: Sieve of Eratosthenes:My Failed Attempt

Posted 13 May 2013 - 05:53 AM

Quote

I'd suggest looking at line 17, I think you increment p1 and then assign too it. The loop condition means this can go beyond the end of the array.


Actually no since he is using the post fix of ++ so he is first assigning to the element then incrementing after that assignment.

his version is the exact same as doing

*p1 = 1;
++p1;

Was This Post Helpful? 0
  • +
  • -

Page 1 of 1