CODEWITHSUNDEEP
c
Wei Guo
Wei Guo

Reputation: 25

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

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;
 }

Upvotes: 1

Views: 74

Answers (1)

francis
francis

Reputation: 9817

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 !

Upvotes: 3

Related Questions