埃拉托斯特尼筛法C代码报错排查与修正请求

问题描述 #

我用埃拉托斯特尼筛法编写了一段查找素数的C语言代码，部分数字运行正常，但部分数字会触发未定义错误，表现为程序卡死（看起来像无限要求输入初始值n），小数字和部分大数字都会触发这个问题。附上原代码，请求排查错误原因、修正代码并告知预防方法。

原代码 #

#include <stdio.h>
int main()
{
    int n;
    printf("enter number: ");
    scanf("%d",&n);
    int arr[n],pr=2;
    for(int i=0;pr<=n;i++)
    {
        arr[i]=pr;
        pr++;
    }
    int j,k=0;
    while(arr[k]<=n)
    {
        for(j=2;j<n;j++)
        {
            for(k=0;k<n;k++)
            {
                if(arr[k]%j==0 && arr[k]>j)
                    arr[k]=0;
            }
        }
    }
    for(int i=0;i<n;i++)
    {
        if(arr[i]>0)
            printf(" %d",arr[i]);
    }
    printf("\n");
    return 0;
}

错误原因分析 #

1. 无限循环触发：while(arr[k]<=n)的条件存在致命缺陷。当arr[k]被标记为0后，0始终小于等于输入的正整数n，导致这个while循环永远无法终止，程序直接卡死。
2. 数组初始化与越界风险：
   • 变长数组arr[n]的大小为n，但初始化时仅填充了n-1个元素（从2到n），剩余的arr[n-1]位置会残留垃圾值，访问这些垃圾值会引发未定义行为。
   • 当输入n=1时，pr=2>1，初始化循环完全不执行，整个数组都是垃圾值，后续循环访问时会出现不可预测的错误。
3. 筛法逻辑完全偏离：埃拉托斯特尼筛法的核心是从当前素数的倍数开始标记非素数，但你的代码中每次遍历所有j值并检查所有数组元素，不仅效率极低，还会错误标记部分数值。

修正后的代码 #

以下是符合埃氏筛逻辑、修复所有问题的代码：

#include <stdio.h>
#include <stdlib.h> // 用于malloc/free

int main()
{
    int n;
    printf("enter number: ");
    // 输入验证，确保n是正整数
    if (scanf("%d", &n) != 1 || n < 2) {
        printf("请输入大于等于2的正整数\n");
        return 1;
    }

    // 用动态分配内存替代变长数组，避免栈溢出和越界风险
    int *is_prime = (int*)malloc(n * sizeof(int));
    if (is_prime == NULL) {
        printf("内存分配失败\n");
        return 1;
    }

    // 初始化数组：1表示是素数，0表示非素数
    for (int i = 0; i < n; i++) {
        is_prime[i] = 1;
    }
    // 0和1不是素数
    is_prime[0] = is_prime[1] = 0;

    // 埃拉托斯特尼筛法核心逻辑
    for (int i = 2; i * i <= n; i++) {
        if (is_prime[i] == 1) { // 如果i是素数，标记其所有倍数
            for (int j = i * i; j < n; j += i) {
                is_prime[j] = 0;
            }
        }
    }

    // 输出所有素数
    printf("素数列表：");
    for (int i = 2; i < n; i++) {
        if (is_prime[i] == 1) {
            printf(" %d", i);
        }
    }
    printf("\n");

    // 释放动态分配的内存
    free(is_prime);
    return 0;
}

预防方法 #

• 严谨处理循环条件：确保每个循环都有明确的终止条件，避免依赖可能被修改的变量作为判断依据。
• 避免变长数组的潜在问题：变长数组在栈上分配，容易引发栈溢出，建议用malloc动态分配内存，同时记得用完后释放。
• 遵循算法核心逻辑：实现经典算法前先理清步骤，不要凭直觉编写逻辑，埃氏筛的核心是标记素数的倍数而非逐一检查所有数值。
• 增加输入验证：对用户输入的数值做合法性检查，避免非法输入（如负数、1、非整数）导致的未定义行为。
• 初始化所有变量/数组：永远不要使用未初始化的变量或数组元素，避免垃圾值引发的不可预测错误。

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