segmentation fault - Prime Finder in C -
my prime finder based on fact check if number prime, need check prime numbers it's square root. so, find every prime number between 0 , x, knowing prime numbers between 0 , x's square root allow compute things quickly. initial list of prime finders find using brute force method, pass list quick prime finder.
this code compiles , works correctly, reason i'm getting segmentation fault 11 when try upper bound of 5 million or more. seems "all good" until try make "finalprimes" list. thoughts why might be/general feedback appreciated. ps, i'm new c general commentary on design appreciated 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); /* user input upper bound */ int boundroot = (int) sqrtf((float) upperbound) + 1; /* root of upper bound later use */ printf("%i root\n", boundroot); printf("all good\n"); int initialprimes[boundroot / 2]; /* can safely assume number of primes between 0 , x less x / 2 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 , %i\n", initialprimessize, boundroot); printf("all good\n"); initialprimes[initialprimessize] = 50000; printf("all good\n"); printf("\nhere are: \n"); /* act barrier between primes , trailing 0's is_prime_quick works */ (int x = 0; x < initialprimessize; x++) { printf("%i\n", initialprimes[x]); } fill_array_with_primes_quick(initialprimes, finalprimes, boundroot, upperbound); printf("\nhere 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 number want primes */ { array[0] = 2; array[1] = 3; /* fill array 2 & 3 cos yolo */ int arraycount = 2; /* start counter cos c doesn't have arraylists */ (int pote = 4; pote < upper; pote++) /* every number in range potentially prime */ { if (is_prime_brute(pote)) { array[arraycount] = pote; arraycount++; } } } bool is_prime_brute(int num) { (int x = 2; x < (int) sqrtf((float) num) + 1; x++) /* go through numbers number's square root looking factor */ { if (num % x == 0) { return false; /* has factor, not prime */ } } return true; /* if we've made far it's prime */ } void fill_array_with_primes_quick(int *initial, int *final, int lower, int upper) { int arraycount = 0; (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 number we're @ in array less number's square root */ { if (num % primes[pos] == 0) { return false; } pos++; } return true; } int find_end(int *array, int length) /* find true end of array, contain few trailing 0's */ { for(int x = 0; x < length; x++) { if (array[x] == 0) { return x; } } return 0; }
this happens because allocate memory in automatic memory area (also known "on stack").
replace these declarations 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 boundroot / 2. add calls free both allocated arrays: after final while loop in main, add
free(initialprimes); free(finalprimes); 
Comments
Post a Comment