C 中的素数查找器

Question

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

此代码可以正确编译和工作，但由于某种原因，当我尝试使用 500 万或更多的上限时，出现分段错误 11。在我尝试制作 "finalPrimes" 列表之前，它似乎是 "all good"。非常感谢任何关于为什么可能 be/general 反馈的想法。 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

出现这种情况是因为你在自动内存区（也称为"on the stack"）分配了太多内存。

将这些声明替换为 mallocs:

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

成为

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

同时将 sizeof initialPrimes / sizeof initialPrimes[0]) 表达式替换为 boundRoot / 2。还为两个分配的数组添加对 free 的调用：在 main 中的最终 while 循环之后，添加

free(initialPrimes);
free(finalPrimes);

Answer 2

5m的平方根大约是2236，所以是栈溢出。不过您的代码似乎是安全的，因此分段错误不是由任何未定义的行为引起的：

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];当你声明和定义自动可变长度数组时。

VLA驻留在栈上，栈space比较小

要解决此问题，您应该使用 malloc 在堆上手动分配 space。

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

当你用完它们后，别忘了free记忆。

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

例如下面是使崩溃消失的声明：

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

C 中的素数查找器

Prime Finder in C

c

primes

segmentation-fault