C program : crashes for values greater than 0.3 million

Question

This program is to find the prime number which is is the sum of most number of consecutive prime numbers. When I set the value of LIMIT to 50 100 or even 1000, the correct values are obtained. But if I take the value of LIMIT greater than 0.3 million the program crashes. What is the reason behind this problem and how can I solve it?

#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#define LIMIT 300000
//binary search function

int Bsearch(long long int *arr,long long int low,long long int high,long long int search)
{
    if(high<low)
        return 0;

    long long int mid = (low+high)/2;

    if(search<arr[mid])
    {return(Bsearch(arr,low,mid-1,search));}

    else if(search>arr[mid])
    {return(Bsearch(arr,mid+1,high,search));}

    else if(search==arr[mid]) return 1;

    else return 0;
}

int main()
{
    long int arr[LIMIT];

    arr[0]=0;arr[1]=1;

    for(long long int i=2;i<=LIMIT;i++)
    {arr[i]=1;}

    long long index=2;

    for(long long int i=3;i<=LIMIT;i++,index++)
    {
        for(long long int j=2;j<=sqrt(i);j++)
        {
            if(i%j==0)
            {arr[index]=0;}
        }
    }
    long long int count=0;
    //calculate total primes
    for(long int A=0;A<LIMIT;A++)
    {
        if(arr[A]==1)
            count++;
    }

    //all primes stored in seperate primes array
    long long int primes[count];
    for(long int A=0,index=0;A<LIMIT;A++)
    {
        if(arr[A]==1)
        {
            primes[index++]=A+1;
        }
    }

    long long int primes_sum[count];
    primes_sum[0]=primes[0];
    for(long long int B=1;B<count;B++)
    {primes_sum[B]=primes_sum[B-1]+primes[B];}

    for(long long int i =0;i<(sizeof(primes)/sizeof(long long int));i++)
    {
        printf("\nprime number : %lld\tprimes_sum : %lld",primes[i],primes_sum[i]);
    }

    struct ultimata
    {
        long long int num_of_primes;
        long long int prime_number;     
    }final;

    final.num_of_primes=0;final.prime_number=0;
    for(long long int j=(sizeof(primes_sum)/sizeof(long long int))-1;j>=2;j--)
    {
        for(long long int i=j-2;i>=1;i--)
        {
            long long int search_term = primes_sum[j]-primes_sum[i];
            printf("\nsearch term : %lld (primes_sum[%lld]-primes_sum[%lld])",search_term,j,i);
            if(search_term>LIMIT)
                break;
            if(Bsearch(primes,0,(sizeof(primes)/sizeof(long long int)),search_term))
            {
                printf("\nfound! : %lld terms : %lld",search_term,j-i-1);
                if((j-i-1)>final.num_of_primes)
                {
                    printf("\nfound! : %lld",search_term);
                    final.prime_number=search_term; 
                            final.num_of_primes=j-i-1;
                }   
            }
        }
    }

    printf("Largest prime number : %lld",final.prime_number,final.num_of_primes);
    return 0;
}

Make `arr` global variable (if you don't care about style), or use `malloc`, since it is likely that the array uses more than the size of the stack. You are on Windows, right? — nhahtdh, Jan 19 '14 at 20:26
@nhahtdh Yeah you are right after declaring arr outside main, this error does not occur..ty — user2876907, Jan 19 '14 at 20:40
If you are writing this code just for fun, then whichever way is fine, since they fix the problem. But if you are writing this as homework or if you encounter the same problem with a real program to be used by other people, then use `malloc`, since you can reclaim the memory after the operation (and avoid polluting the global scope). — nhahtdh, Jan 19 '14 at 20:55

score 1 · Accepted Answer · answered Jan 19 '14 at 20:27

1

I think one of your problems is in these lines (multiple times in other places, too):

long int arr[LIMIT];

...

for(long long int i=2;i<=LIMIT;i++)
{arr[i]=1;}

Your array has LIMIT entries, but you try to write to entry LIMIT+1. C starts with array index 0 and ends with size-1. I don't know why it works for smaller values of LIMIT.

answered Jan 19 '14 at 20:27

usr1234567

21,601
16
108
128

No even after correcting it the program still crashes. – user2876907 Jan 19 '14 at 20:39
@user2876907 As I said, that was one of the errors. Give the answers of the question mentioned by the comments a try. They look promising. If you are sure that you have an other problem, reopen this question or create a new one describing your new problem. – usr1234567 Jan 19 '14 at 20:42
@user2876907 Yeah you said it right, it was one of the errors, and you were helpful one aspect of the problem, I thank you for that..ty – user2876907 Jan 19 '14 at 20:45

C program : crashes for values greater than 0.3 million

1 Answers1