生成1-100素数的C程序运行异常，请求问题排查与解决

问题分析 #

你的程序存在几个核心逻辑错误，导致无法正确生成素数：

• 素数判断逻辑错误：内层循环中，只要单次取余不为0就立即将数存入素数数组并递增索引，这会导致同一个数被多次写入，且未完成所有必要检查就提前判定为素数。比如i=5时，j=2取余不为0就直接存入，但实际上应该等内层循环完整执行（没有触发break），确认没有任何因数后，才判定为素数存入数组。
• 素数检查范围计算错误：a = i / primeindex完全不合理，primeindex是当前已找到的素数个数，不是用来计算检查上限的数值。正确的素数检查上限应该是i的平方根（因为如果n有一个大于平方根的因数，必然对应一个小于平方根的因数），或者遍历已找到的素数直到其平方大于i。
• 内层循环遍历对象错误：原代码从j=2开始遍历所有数到a，这会重复检查非素数的除数（比如j=4、6等），既低效又容易出错。正确的做法是遍历已找到的素数，因为如果一个数能被非素数整除，那它必然能被该非素数的某个素因数整除，只需检查素数即可。
• 输出数组越界：1-100之间的素数只有25个，而你定义的数组大小是50，输出时循环i <= 50会访问到未初始化的数组元素，输出垃圾值。

修正后的代码 #

#include<stdio.h>
#include<stdlib.h>
#include<math.h> // 用于sqrt函数

int main() {
    int primenum[25]; // 1-100的素数共25个，数组大小足够即可
    int i, j;
    int primeindex = 2;

    primenum[0] = 2;
    primenum[1] = 3;

    // 生成并检查奇数
    for (i = 5; i <= 100; i += 2) {
        int is_prime = 1; // 标记是否为素数
        int sqrt_i = sqrt(i); // 计算检查上限：i的平方根

        // 遍历已找到的素数，直到素数大于平方根
        for (j = 0; primenum[j] <= sqrt_i; j++) {
            if (i % primenum[j] == 0) {
                is_prime = 0;
                break;
            }
        }

        // 如果是素数，存入数组
        if (is_prime) {
            primenum[primeindex] = i;
            primeindex++;
        }
    }

    // 输出所有素数
    printf("1-100之间的素数：\n");
    for (i = 0; i < primeindex; i++) {
        printf("%d ", primenum[i]);
    }
    printf("\n");

    return 0;
}

修正说明 #

1. 素数判断逻辑：新增is_prime标记，初始为1（假设是素数），如果找到能整除i的素数，就将标记设为0并跳出循环。只有当循环结束后标记仍为1时，才将i存入素数数组。
2. 检查范围优化：使用sqrt(i)获取检查上限，避免不必要的计算；同时遍历已找到的素数，而非所有整数，提升效率。
3. 数组与输出优化：根据1-100素数的实际数量（25个）定义数组大小，输出时仅遍历已存入的素数（通过primeindex控制范围），避免访问未初始化元素。

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