使用Code::Blocks+GCC实现埃氏筛求200万内素数和遇问题求助

问题背景 #

离开编程20年的回归开发者，为Project Euler题目编写程序，计算200万以内所有素数的和，采用埃拉托斯特尼筛算法，使用Code::Blocks搭配GNU GCC编译器。代码在L小于1000000时正常运行，超过后无法工作，同时出现long long int相关警告。

原代码 #

#include <stdio.h>
#define L 2000000
int main()
{
    unsigned long long int i, j, n, num[L], sum = 0;
    for (i = 0; i < L; i++)
        num[i] = i + 1;

    for (j = 2; j*j <=L; j++)
        {
            for (n = j; n*j<=L; n++)
                {
                    num[n * j - 1] = 0;
                }
        }
    for (i = 1; i < L; i++)
        {
            if (num[i] != 0)
                {
                    printf("%llu\n",num[i]);
                    sum = sum + num[i];
                }
        }
    printf("%llu\n", sum);
    return 0;
}

错误信息 #

***||=== Build file: Debug in 2MILLIONPRIMESUM (compiler: GNU GCC Compiler) ===|

***E:\Code Blocks Projects\2MILLIONPRIMESUM\main.c||In function 'main':|

E:\Code Blocks Projects\2MILLIONPRIMESUM\main.c|22|warning: unknown conversion type character 'l' in format [-Wformat=]|

E:\Code Blocks Projects\2MILLIONPRIMESUM\main.c|22|warning: too many arguments for format [-Wformat-extra-args]|******

解决步骤 #

1. 解决printf格式符警告 #

警告源于编译器默认使用C89标准，而long long类型是C99才引入的，导致%llu格式符不被识别。

解决方法：

• 在Code::Blocks中设置编译选项：打开项目的Build Options -> Compiler Settings -> Other Options，添加-std=c99（或更高版本如-std=c11），强制编译器使用C99及以上标准。

2. 解决L超过1e6时程序崩溃问题 #

你在栈上声明了大小为2000000的unsigned long long数组，每个元素占8字节，总内存为16MB。而Windows平台默认栈大小仅为1MB左右，这种大数组会导致栈溢出，直接引发程序崩溃。

有两种解决方式：

方式一：将数组改为全局变量

全局变量存储在全局/静态存储区，不受栈大小限制，只需将数组声明移到main()函数外部：

#include <stdio.h>
#define L 2000000
unsigned long long int num[L]; // 全局数组
int main()
{
    unsigned long long int i, j, n, sum = 0;
    // 后续代码不变
}

方式二：使用动态内存分配

通过malloc在堆上分配内存，用完后用free释放，避免栈溢出：

#include <stdio.h>
#include <stdlib.h> // 引入malloc/free的头文件
#define L 2000000
int main()
{
    unsigned long long int i, j, n, sum = 0;
    // 动态分配内存
    unsigned long long int *num = malloc(L * sizeof(unsigned long long int));
    if (num == NULL) { // 检查内存分配是否成功
        printf("内存分配失败\n");
        return 1;
    }
    // 原初始化、筛法、求和代码不变
    // 最后释放内存
    free(num);
    return 0;
}

3. 优化建议：减少内存占用 #

原代码用unsigned long long数组存储数字，内存浪费严重。埃氏筛只需标记是否为素数，用布尔数组（每个元素1字节）即可，200万元素仅占2MB，彻底避免内存问题：

#include <stdio.h>
#define L 2000000
_Bool num[L]; // 全局布尔数组，内存占用仅2MB
int main()
{
    unsigned long long sum = 0;
    // 初始化：所有数标记为素数（1）
    for (int i = 0; i < L; i++) {
        num[i] = 1;
    }
    num[0] = 0; // 1不是素数
    // 埃氏筛核心逻辑
    for (unsigned long long j = 2; j*j <= L; j++) {
        if (num[j-1]) { // 仅处理素数的倍数
            for (unsigned long long n = j; n*j <= L; n++) {
                num[n*j - 1] = 0;
            }
        }
    }
    // 计算素数和
    for (int i = 1; i < L; i++) {
        if (num[i]) {
            sum += (i+1);
        }
    }
    printf("%llu\n", sum);
    return 0;
}

内容的提问来源于stack exchange，提问作者Vinayak Deshmukh