В настоящее время я изучаю C и недавно практиковался в Codewars. Я столкнулся с этим вопросом о главных пробелах и мне было интересно, как его улучшить. Первоначально я был одурачен, думая, что это не будет так плохо, но я понял, что найти простые числа сложно (особенно для больших чисел, где это может быть как минимум проблема NP-Hard). Я знаю, что мой код сейчас имеет несколько циклов for, и это ужасно с точки зрения производительности. Я также не до конца знаю чистые способы написания C, поэтому, возможно, некоторые из них были запрещены (например, я знаю, что я обязан освободить динамически выделенную память, но я попытался освободить память в вызывающей функции main ()). и освобождая первый элемент выделенного блока памяти - не уверен, является ли это подходящим способом освобождения блока памяти)
В общем случае основная функция вызывает функцию prime_gap несколько раз. Я знаю, что этот код работает, потому что он был успешно отправлен, но есть ли какие-нибудь советы по написанию этого лучше (алгоритмически в 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;
}