segmentation fault in number of prime up to N(N>10000)

Question

I am having a segmentation fault on my program seeking the number of prime numbers up to N.

I used a dynamic linked list for the prime numbers to test N for efficiency.

The problem is it works when N<=17508. It fails for greater N. Especially when I add up the print out, it always have segmentation fault. Can anyone help? Thanks.

#include <stdio.h>
#include <stdlib.h>
#include <math.h>

typedef struct prime{
long value;
struct prime *next;
}prime;

long numofprime(long n)
{
long a, b, c;

prime *head, *p1, *p2, *p3;
int flag;

if(n<0)
n=-n;

if(n<2)
    return 0;
else if(n==2)
    return 1;
else
{/*creat linked list*/
   p1=(prime *)malloc(sizeof(prime));
   p1->value=2;
   p1->next=NULL;
   p2=p1;
   head=p1;

        b=1;
        for(a=3;a<=n;a+=2)
        {
            flag=0;
            p3=head;
            while(p3!=NULL)
            {
                c=p3->value;
                if(a%c==0)
                {
                    flag=1;
                    break;
                }
                p3=p3->next;
            }

            if(flag==0)
            {/*add prime number to the linked list*/
                p1=(prime *)malloc(sizeof(prime));
                p1->value=a;
                p2->next=p1;
                p2=p1;
                b++;
            }
        }

        c=0;
        while(head!=NULL)
        {
            printf("%5ld ", head->value);
            if(c%15==0) printf("\n");
            head=head->next;
            c++;
        }

        return b;
    }

}

int main(int argc, char *argv[])
{

long n;
long np;

if(argc<2)
{
    printf("Please input the max num!\n");
    exit(0);
}
else if(argc>2)
{
    printf("Too many arguments!\n");
    exit(0);
}
else
    n=strtol(argv[1], NULL, 10);

    np=numofprime(n);

    printf("\n\nthere are %ld primes < n!\n", np);

    return 0;
 }

When you run in a debugger, where does it say the crash is? Do all variables involved in that expression look okay to you? — Some programmer dude, Jul 12 '15 at 07:38
When `N` goes above 17508, how many nodes have you allocated then? You are aware of that memory allocation can fail, and `malloc` retrurn `NULL`? You need to check for that. Also, [in C don't cast the return of `malloc`](http://stackoverflow.com/questions/605845/do-i-cast-the-result-of-malloc). — Some programmer dude, Jul 12 '15 at 07:47
Upon 17508, there are 2014 prime numbers, 2014 nodes in the linked list. Thanks Joachim and Jens — Wei Guo, Jul 12 '15 at 07:51

francis · Answer 1 · 2015-07-12T07:57:04.383

3

As you allocate a new item for the linked list, always set the pointer to the next item to NULL. Otherwise, the end of the linked list cannot be detected, an undefined behavior appears and segmentation faults are possible.

For instance :

        {/*add prime number to the linked list*/
            p1=malloc(sizeof(prime));
            if(p1==NULL){fprintf(stderr,"failed to allocate\n");exit(1);}
            p1->value=a;
            p1->next=NULL; ///this new line here
            p2->next=p1;
            p2=p1;
            b++;
        }

Moreover, do not forget to free() the memory at the end of the function. Doing head=head->next to print the linked list will not ease this operation since going back is not possible : the pointer to the beginning of the linked list is lost. Always keep a pointer to the beginning of a linked list somewhere !

edited Jul 12 '15 at 07:57

answered Jul 12 '15 at 07:49

francis

9,525
2
25
41

Good point. Is this code time complexity o(N(logN)? I have no knowledge about this. – Wei Guo Jul 12 '15 at 08:07
There are about ln(n) prime numbers below n. So the total number of operations is about \sum_{n=1}^N(ln(n)). And this sum is about N.ln(N)-N. So the complexity of your program is O(N.ln(N)). Notice that you can `break` the while loop as soon as `p3->value` is above `sqrt(a)`. It will not change the complexity, but it might divide the computation time by 2. – francis Jul 12 '15 at 08:23

segmentation fault in number of prime up to N(N>10000)

1 Answers1