0

I'm currently learning C and have been practicing on codewars recently. I came across this question on prime gaps and was curious on how to improve it. I was initially fooled in thinking this wouldn't be as bad but I realized that finding primes is difficult (especially for large numbers where it can be at least an NP-Hard problem). I know my code right now has multiple for-loops and this is terrible in terms of performance. I also don't fully know the clean ways of writing C so there might be some no-nos I did (e.g. I know it's my responsibility to free up dynamically allocated memory but I tried freeing memory in the main() calling function and by freeing the first element of the allocated memory block--not sure if this is the appropriate way of freeing up a block of memory)

In general, the main function calls the prime_gap function several times. I know this code works because it was submitted successfully but any tips on writing this better (algorithmically in C)? 

/* a prime gap of length "n" indicates that n-1 consecutive composite numbers exist between two primes. 
 * For example, the gap beween (2,3) is 1, the gap between (5,7) is 2 and the gap between (7,11) is 4. 
 * Our function should return the first pair of primes that satisfies the gap that we're looking for in a search between two numbers. /


There should also be no primes that exist within the gap of the first two primes that are found. 
 * gap(g, n, m) -> where g = gap length, n = start of search space, m = end of search space 
 */

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

long long *gap(int g, int n, int m);
bool check_prime(int, bool);

int main(int argc, const char *argv[]){
        long long *check3 = gap(2,100,110);
        for (int i = 0; i < 2; i++){
                printf("%lld ", check3[i]);
        }
        free(&check3[0]);

        printf("\n");

        long long *check = gap(2,3,50);
        for (int i = 0; i< 2; i++){
                printf("%lld ", check[i]);
        }
        printf("\n");
        free(&check[0]);

        long long *check1 = gap(2,5,5);
        for (int i = 0; i < 2; i++){
                printf("%lld ", check1[i]);
        }
        free(&check1[0]);
        printf("\n");

        long long *check2 = gap(4,130,200);
        for (int i = 0; i < 2; i++){
                printf("%lld ", check2[i]);
        }
        free(&check2[0]);
        printf("\n");

        long long *check4 = gap(6,100,110);
        for (int i = 0; i < 2; i++){
                printf("%lld ", check4[i]);
        }
        free(&check4[0]);
        printf("\n");

 long long *gap(int g, int n, int m) {

        long long *result = (long long*) malloc(sizeof(long long) *2); // dynamically allocate 2 long longs for the integer array 
        if (result == NULL){
                perror("Not enough memory");
        }
        int test = 0;
        static bool prime;

        for (int i = n; i < m; i++) {  // traverse search space 
                prime = true;
                prime = check_prime(i, prime);
                if (prime == true) { // identifies prime number
                        test = i + g; // add the gap value to identified prime 
                        prime = false; // set bool to false to now check for any primes that exist between i and i+gap 
                        for (int z = i+1; z < test; z++ ) {    // check there is no prime in between the first and second (test) primes 
                                prime = check_prime(z, prime);
                                if (prime == true) break;
                        }
                        if (prime != true) {   // found no primes between i and i+gap
                                prime = true; // set bool to true to then toggle off in the check right below if i+gap is not actually prime
                                prime = check_prime(test, prime);   // now need to check whether i+gap itself is a prime
                                if (prime == true) {
                                        result[0] = i; result[1] = test;
                                        return result;
                                }
                        }
                }
        }
        result[0] = result[1] = 0;
        return result;
}

bool check_prime(int i, bool prime){
        for (int j = 2; j <= sqrt(i); j++){
                if (i % j == 0) {
                        return false;
                }
        }
        return true;
}
user6461080
  • 129
  • 7

1 Answers1

1

Reading you code, the following comments come to mind:

  • you are never freeing the space allocated by the malloc
    • therefore I am wondering if you really need to use malloc, a simple global variable would have been sufficient for what you are doing with it
  • you check_prime function has a second parameter prime that is never used
  • in function gap, the variable prime is indicated as static, this is not required, it could also lead to errors
  • from the algorithmic point of view:
    • your logic goes like
for i in range to check:
    if i is prime
      check if all the number between i and i+gap are not prime
      if i+gap is prime then return the tuple(i, i+gap)
  • globally, you are checking several times for the same number if it is prime, since this is by far the most "expensive" operation, you should try not to
  • specifically, you should start by checking test before iterating over all the numbers in the range i..test.
Louis Caron
  • 1,043
  • 1
  • 11
  • 17