Prime Finder in C

Question

My prime finder is based on the fact that to check if a number is prime, we only need to check the prime numbers up to it's square root. So, to find every prime number between 0 and x, knowing all the prime numbers between 0 and x's square root will allow us to compute things very quickly. This initial list of prime finders we find using the brute force method, then we pass this list into the quick prime finder.

This code compiles and works correctly, but for some reason I'm getting segmentation fault 11 when I try an upper bound of 5 million or more. It seems to be "all good" until I try to make the "finalPrimes" list. Any thoughts as to why this might be/general feedback is greatly appreciated. PS, I'm new to C so general commentary on my design is appreciated as well.

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

void fill_array_with_primes_brute(int *array, int upper);

void fill_array_with_primes_quick(int *initial, int *final, int lower, int upper);

int find_end(int *array, int length);

bool is_prime_brute(int num);

bool is_prime_quick(int *primes, int num);



int main(void)
{
  int upperBound;
  printf("Enter upper bound: \n");
  scanf("%i", &upperBound);                               /* get user input for upper bound */
  int boundRoot = (int) sqrtf((float) upperBound) + 1;    /* get the root of this upper bound for later use */
  printf("%i is root\n", boundRoot);
  printf("All good\n");
  int initialPrimes[boundRoot / 2];                       /* we can safely assume that the number of primes between 0 and x is less than x / 2 for larger numbers */
  printf("All good\n");
  int finalPrimes[upperBound / 2];
  printf("All good\n");
  fill_array_with_primes_brute(initialPrimes, boundRoot);
  printf("All good\n");
  int initialPrimesSize = find_end(initialPrimes, sizeof initialPrimes / sizeof initialPrimes[0]);
  printf("All good\n");
  printf("%i primes between 0 and %i\n", initialPrimesSize, boundRoot);
  printf("All good\n");
  initialPrimes[initialPrimesSize] = 50000;
  printf("All good\n");
  printf("\nHere they are: \n");               /* This will act as a barrier between the primes and the trailing 0's so that is_prime_quick works properly */
  for (int x = 0; x < initialPrimesSize; x++)
  {
    printf("%i\n", initialPrimes[x]);
  }
  fill_array_with_primes_quick(initialPrimes, finalPrimes, boundRoot, upperBound);
  printf("\nHere are the other ones: \n");
  int pos = 0;
  while (finalPrimes[pos] != 0)
  {
    printf("%i\n", finalPrimes[pos]);
    pos++;
  }
}

void fill_array_with_primes_brute(int *array, int upper)      /* upper is the number up to which we want primes */
{
  array[0] = 2;
  array[1] = 3;                                   /* fill array with 2 & 3 cos yolo */
  int arrayCount = 2;                             /* start this counter cos C doesn't have ArrayLists */
  for (int pote = 4; pote < upper; pote++)           /* every number in range is potentially a prime */
  {
    if (is_prime_brute(pote))
    {
      array[arrayCount] = pote;
      arrayCount++;
    }
  }
}

bool is_prime_brute(int num)
{
  for (int x = 2; x < (int) sqrtf((float) num) + 1; x++)    /* go through numbers up to the number's square root looking for a factor */
  {
    if (num % x == 0)
    {
      return false;                                /* has a factor, so not a prime */
    }
  }
  return true;                                     /* if we've made it this far it's a prime */
}

void fill_array_with_primes_quick(int *initial, int *final, int lower, int upper)
{
  int arrayCount = 0;
  for (int pote = lower; pote < upper; pote++)
  {
    if (is_prime_quick(initial, pote))
    {
      final[arrayCount] = pote;
      arrayCount++;
    }
  }
}

bool is_prime_quick(int *primes, int num)
{
    int pos = 0;
    while (primes[pos] < (int) sqrtf((float) num) + 1)     /* while the number we're at in the array is less than the number's square root */
    {
      if (num % primes[pos] == 0)
      {
        return false;
      }
      pos++;
    }
    return true;
}

int find_end(int *array, int length)               /* Find the true end of the array, as it will contain a few trailing 0's  */
{
  for(int x = 0; x < length; x++)
  {
    if (array[x] == 0)
    {
      return x;
    }
  }
  return 0;
}

Answer 1

The crash happens here: int finalPrimes[upperBound / 2]; when you declare and define automatic variable length array.

1. VLA resides on the stack, and stack space is relatively small.

To solve the problem, you should manually allocate space on the heap using malloc instead.

int* initialPrimes = malloc(sizeof(int)*(upperBound / 2));                       
int* finalPrimes = malloc(sizeof(int)*(upperBound / 2));

and when you are done with them, don't forget to free the memory.

Note that if you declare the array as global variables (with some constant yet big size) then the compiler will allocate them for you.

For instance the following is declaration make the crash vanish:

int finalPrimes[5000001];
int initialPrimes[5000001];
int main(void){
    ....

Answer 2

This happens because you allocate too much memory in the automatic memory area (also known as "on the stack").

Replace these declarations with mallocs:

int initialPrimes[boundRoot / 2];
int finalPrimes[boundRoot / 2];

become

int *initialPrimes = malloc(sizeof(int)*boundRoot / 2);
int *finalPrimes = malloc(sizeof(int)*boundRoot / 2);

Also replace sizeof initialPrimes / sizeof initialPrimes[0]) expression with boundRoot / 2. Also add calls to free for both allocated arrays: after the final while loop in main, add

free(initialPrimes);
free(finalPrimes);

Answer 3

The square root of 5m is about 2236, so it is a stack overflow. Your code seems to be safe though, so the segmentation fault isn't caused by any undefined behavior:

Enter upper bound: 
5000000
2237 is root
All good
All good
ASAN:DEADLYSIGNAL
=================================================================
==24998==ERROR: AddressSanitizer: stack-overflow on address 0x7ffe01f4fb28 (pc 0x55d6add011dd bp 0x7ffe028da410 sp 0x7ffe01f4fb30 T0)
    #0 0x55d6add011dc in main (/tmp/a.out+0x11dc)
    #1 0x7fbb442fb4c9 in __libc_start_main (/usr/lib/libc.so.6+0x204c9)
    #2 0x55d6add00d19 in _start (/tmp/a.out+0xd19)

SUMMARY: AddressSanitizer: stack-overflow (/tmp/a.out+0x11dc) in main
==24998==ABORTING

As @dasblinkenlight mentioned, you may fix it using heap allocation. However, also consider one of the primality test algorithm, which is way faster and more scalable, but some aren't proved to be 100% correct (it's actually used for crypto).