C中的总体搜索器

Question

我的主要搜索器基于这样一个事实，即要检查一个数是否为素数，我们只需检查质数达到平方根即可。因此，要找到0到x之间的每个素数，知道0和x的平方根之间的所有素数将使我们能够快速计算事物。我们使用强力方法找到的主要搜索引擎的初始列表，然后我们将这个列表传递给快速搜索引擎。

此代码编译并正常工作，但由于某种原因，当我尝试使用500万或更多的上限时，出现了段错误11。在我尝试制作“finalPrimes”名单之前，它似乎是“一切都好”。任何想法，为什么这可能是/一般反馈，不胜感激。 PS，我是C新手，所以我的设计的一般评论也很感激。

#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

发生这种情况是因为您在自动内存区域（也称为“堆栈”）中分配了太多的内存。

与malloc小号替换这些声明：

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

成为

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

还与boundRoot/2替换sizeof initialPrimes/sizeof initialPrimes[0])表达。在main最终while循环之后，添加

free(initialPrimes); 
free(finalPrimes); 

Answer 2

5米的平方根大约是2236，所以它是一个堆栈溢出：还呼吁增加free两个分配的数组。您的代码似乎是安全的，所以分割故障不受任何不确定的行为引起：

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 

正如@dasblinkenlight提到的，你可以使用堆分配修复它。但是，也要考虑primality test algorithm之一，它的速度更快，可扩展性更高，但有些未被证明是100％正确的（它实际上用于加密）。

Answer 3

崩溃发生在这里：int finalPrimes[upperBound/2];当你声明和定义自动变长数组。

1. VLA驻留在堆栈上，堆栈空间相对较小。

要解决该问题，您应该使用malloc替代手动分配堆上的空间。

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

，当你与他们所做的，不要忘了free内存。

请注意，如果您将数组声明为全局变量（具有一些常量但大小），那么编译器会为您分配它们。

例如，下面的声明做出崩溃消失：

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