C program stops responding for large inputs

Question

I am (re-)learning C and in the book I am following we are covering arrays, and the book gives an algorithm for finding the first n primes; myself being a mathematician and a decently skilled programmer in a few languages I decided to use a different algorithm (using the sieve of Eratosthenes) to get the first n primes. Well making the algorithm went well, what I have works, and even for moderately large inputs, i.e. the first 50,000 primes take a bit to run as you would expect, but no issues. However when you get to say 80,000 primes pretty much as soon as it begins a window pops up saying the program is not responding and will need to quit, I made sure to make the variables that take on the primes were unsigned long long int, so I should still be in the acceptable range for their values. I did some cursory browsing online and other people that had issues with large inputs received the recommendation to create the variables outside of main, to make them global variables. I tried this for some of the variables that I could immediately put outside, but that didn't fix the issue. Possibly I need to put my arrays isPrime or primes outside of main as well? But I couldn't really see how to do that since all of my work is in main.

I realize I should have done this with separate functions, but I was just writing it as I went, but if I moved everything into separate functions, my arrays still wouldn't be global, so I wasn't sure how to fix this issue.

I tried making them either static or extern, to try and get them out of the stack memory, but naturally that didn't work since they arrays change size depending on input, and change over time.

the code is:

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

unsigned long long int i,j;
unsigned long long int numPrimes,numPlaces;




int main(void)
{
    bool DEBUG=false;

    printf("How many primes would you like to generate? ");
    scanf("%llu",&numPrimes);

    // the nth prime is bounded by n*ln(n)+n*ln(ln(n)), for n >=6 
    // so we need to check that far out for the nth prime
    if (numPrimes>= 6)
        numPlaces = (int) numPrimes*log(numPrimes)+
                            numPrimes*log(log(numPrimes));
    else 
        numPlaces = numPrimes*numPrimes;

    if(DEBUG)
        printf("numPlaces: %llu\n\n", numPlaces);

    // we will need to check each of these for being prime
    // add one so that we can just ignore starting at 0
    bool isPrime[numPlaces+1];

    // only need numPrimes places, since that is all we are looking for
    // but numbers can and will get large
    unsigned long long int primes[numPrimes];

    for (i=2; i<numPlaces+1;i++)
        isPrime[i] = true; // everything is prime until it isn't

    i=2; // represents current prime
    while (i < numPlaces + 1)
    {
        for (j=i+1;j<numPlaces+1;j++)
        {
            if (isPrime[j] && j%i ==0) // only need to check if we haven't already
            {
                isPrime[j] = false;// j is divisibly by i, so not prime
                if(DEBUG)
                {
                    printf("j that is not prime: %llu\n",j);
                    printf("i that eliminated it: %llu\n\n",i);
                }//DEBUG if
            }//if
        }//for

        // ruled out everything that was divisible by i, need to choose
        // the next i now.

        for (j=i+1;j<numPlaces+2;j++)// here j is just a counter 
        {
            if (j == numPlaces +1)// this is to break out of while
            {
                i = j;
                break;
            }// if j = numPlaces+1 then we are done
            else if (isPrime[j]==true)
            {
                i = j;
                if (DEBUG)
                {
                    printf("next prime: %llu\n\n",i);
                }//DEBUG if
                break;
            }//else if
        }// for to decide i
    }//while

    // now we have which are prime and which are not, now to just get
    // the first numPrimes of them.
    primes[0]=2;
    for (i=1;i<numPrimes;i++)// i is now a counter
    {
        // need to determine what the ith prime is, i.e. the ith true
        // entry in isPrime, 2 is taken care of
        // first we determine the starting value for j

        // the idea here is we only need to check odd numbers of being
        // prime after two, so I don't need to check everything
        if (i<3)
            j=3;
        else if (i % 2 ==0)
            j = i+1;
        else
            j = i;

        for (;j<numPlaces+1;j+=2)// only need to consider odd nums
        {
            // check for primality, but we don't care if we already knew
            // it was prime
            if (isPrime[j] && j>primes[i-1])
            {
                primes[i]=j;
                break;
            }//if, determined the ith prime
        }//for to find the ith prime
    }//for to fill in primes

    // at this point we have all the primes in 'primes' and now we just
    // need to print them

    printf(" n\t\t prime\n");
    printf("___\t\t_______\n");

    for(i=0;i<numPrimes;i++)
    {
        printf("%llu\t\t%llu\n",i+1,primes[i]);
    }//for

    return 0;
}//main

I suppose I could just avoid the primes array and just use the index of isPrime, if that would help? Any ideas would help thanks!

Answer 1

Your problem is here, in the definition of the VLA ("Variable Length Array", not "Very Large Array")

    bool isPrime[numPlaces+1];

The program does not have enough space in the area for local variables for the array isPrime when numPlaces is large.

You have two options:

1. declare the array with a "big enough" size outside of the main function and ignore the extra space
2. use another area for storing the array with malloc() and friends

option 1

#include <stdio.h>

unsigned long long int i,j;
bool isPrime[5000000]; /* waste memory */

int main(void)

option 2

int main(void)
{
    bool *isPrime;

    // ...

    printf("How many primes would you like to generate? ");
    scanf("%llu",&numPrimes);

    // ...

    // we will need to check each of these for being prime
    // add one so that we can just ignore starting at 0
    isPrime = malloc(numPrimes * sizeof *isPrime);

    // ... use the pointer exactly as if it was an array
    // ... with the same syntax as you already have

    free(isPrime);
    return 0;
}

Answer 2

The array you allocate is a stack variable (by all likelihood), and stack size is limited, so you are probably overwriting something important as soon as you hit a certain size threshold, causing the program to crash. Try using a dynamic array, allocated with malloc, to store the sieve.