C语言实现埃氏筛法时大数组引发段错误的解决方法

你遇到的Segment fault本质是栈空间不足：代码里用了变长数组bool pPrimes[n]，这种数组会被分配在程序的栈（stack）上，而栈的默认大小通常只有几MB（比如Linux下一般是8MB左右）。当n达到千万级甚至更大时，数组所需内存会直接超过栈的上限，触发段错误。

解决办法 #

1. 使用堆内存分配（最推荐） #

把栈上的数组改成用malloc分配堆内存，堆的可用空间远大于栈，能轻松支持超大n的需求，记得用完后用free释放内存避免泄漏：

#include <stdio.h>
#include <stdbool.h> 
#include <math.h>
#include <time.h>  
#include <limits.h>
#include <stdlib.h>  // 引入malloc/free所需头文件
     
int main(){
    clock_t t;
    t = clock();

    int n = 1299710;
    
    // 分配堆内存，必须检查是否分配成功
    bool *pPrimes = malloc(n * sizeof(bool));
    if (pPrimes == NULL) {
        printf("内存分配失败\n");
        return 1;
    }
    
    for(int i = 0; i<n; i++){
        pPrimes[i] = true;
    }
    
    pPrimes[0] = false;
    pPrimes[1] = false;

    for(int i = 2; i<sqrt(n); i++){
        if(pPrimes[i]){
            for(int x = i*i; x<n; x+=i){
                pPrimes[x] = false;
            }
        }
    }

    for(int i = 2; i<n; i++){
        if (pPrimes[i]){
            printf("%d\n", i);
        }
    }
    t = clock() - t;
    double time_taken = ((double)t)/CLOCKS_PER_SEC; 
 
    printf("%f", time_taken);

    free(pPrimes);  // 释放堆内存
    return 0;
}

2. 内存压缩优化（支持更大n） #

埃氏筛法中每个元素只需要存布尔状态，可以用位运算压缩内存，比如用unsigned char存储8个状态，把内存占用降到原来的1/8，能支持数倍于原大小的n：

#include <stdio.h>
#include <math.h>
#include <time.h>  
#include <limits.h>
#include <stdlib.h>

// 位操作宏定义
#define SET_BIT(arr, idx)    (arr[idx/8] |= (1 << (idx%8)))
#define CHECK_BIT(arr, idx)  (arr[idx/8] & (1 << (idx%8)))
#define CLEAR_BIT(arr, idx)  (arr[idx/8] &= ~(1 << (idx%8)))

int main(){
    clock_t t = clock();
    int n = 1299710;
    
    // 计算所需字节数（向上取整n/8）
    size_t byte_size = (n + 7) / 8;
    unsigned char *pPrimes = malloc(byte_size);
    if (pPrimes == NULL) {
        printf("内存分配失败\n");
        return 1;
    }
    
    // 初始化所有位为1（默认标记为质数）
    for(size_t i = 0; i < byte_size; i++){
        pPrimes[i] = 0xFF;
    }
    // 0和1不是质数
    CLEAR_BIT(pPrimes, 0);
    CLEAR_BIT(pPrimes, 1);

    for(int i = 2; i < sqrt(n); i++){
        if(CHECK_BIT(pPrimes, i)){
            for(int x = i*i; x < n; x += i){
                CLEAR_BIT(pPrimes, x);
            }
        }
    }

    for(int i = 2; i < n; i++){
        if(CHECK_BIT(pPrimes, i)){
            printf("%d\n", i);
        }
    }

    double time_taken = ((double)(clock() - t))/CLOCKS_PER_SEC; 
    printf("%f", time_taken);

    free(pPrimes);
    return 0;
}

3. 全局数组替代（不推荐超大n） #

如果把数组声明为全局变量，它会被分配在静态存储区（而非栈），静态区空间比栈大，但全局变量会一直占用内存直到程序结束，灵活性不如堆分配，仅适合中等规模的n：

#include <stdio.h>
#include <stdbool.h> 
#include <math.h>
#include <time.h>  
#include <limits.h>   

#define MAX_N 1299710
bool pPrimes[MAX_N];  // 全局数组

int main(){
    clock_t t;
    t = clock();

    int n = MAX_N;
    
    for(int i = 0; i<n; i++){
        pPrimes[i] = true;
    }
    
    pPrimes[0] = false;
    pPrimes[1] = false;

    for(int i = 2; i<sqrt(n); i++){
        if(pPrimes[i]){
            for(int x = i*i; x<n; x+=i){
                pPrimes[x] = false;
            }
        }
    }

    for(int i = 2; i<n; i++){
        if (pPrimes[i]){
            printf("%d\n", i);
        }
    }
    t = clock() - t;
    double time_taken = ((double)t)/CLOCKS_PER_SEC; 
 
    printf("%f", time_taken);

    return 0;
}

内容的提问来源于stack exchange，提问作者Simon Klyvare