C程序: crashes for values greater than 0. 300万

Question

这个程序是求质数，即最多数量的连续质数之和。当我将 LIMIT 的值设置为 50 100 甚至 1000 时，会获得正确的值。但如果我将 LIMIT 的值设置为大于 30 万，程序就会崩溃。这个问题背后的原因是什么？我该如何解决？

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

Answer 1

我认为你的问题之一是在这些方面(在其他地方也多次出现):

long int arr[LIMIT];

...

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

您的数组有 LIMIT 条目，但您尝试写入条目 LIMIT+1。 C 从数组索引 0 开始，以 size-1 结束。 我不知道为什么它适用于较小的 LIMIT 值。