请求解释质数统计算法代码及新手读算法代码的技巧

代码功能与逐行解析 #

这段代码的核心功能是计算区间(N, 2N]内的素数个数，使用经典的**埃拉托斯特尼筛法（埃氏筛）**预处理素数标记，再统计目标区间的素数数量。

完整代码如下：

void func(int N)
{
    int i, j, arr[246913] = { 0,1 };
    for (j = 2; j < 246913 / j; j++)
    {
        if (arr[j] == 1)
            continue;
        for (i = j * j; i < 246913; i += j)
            if (i % j == 0)
                arr[i] = 1;
    }

    int cnt = 0;
    for (i = N + 1; i <= N * 2; i++)
        if (arr[i] == 0)
            cnt++;
    printf("%d", cnt);
}

int main()
{
    func(7);
    func(0);
    func(4);
    func(9);
}

逐段解析：

1. 素数标记数组初始化
   int arr[246913] = { 0,1 };

   • 数组arr的下标对应具体数字，比如arr[5]代表数字5
   • 数组值的规则：0表示该数字是素数，1表示非素数（合数或1这类特殊数）
   • 初始化时arr[1]=1（1不是素数），其余元素默认值为0

2. 埃氏筛预处理素数

   for (j = 2; j < 246913 / j; j++)
   {
       if (arr[j] == 1)
           continue;
       for (i = j * j; i < 246913; i += j)
           if (i % j == 0)
               arr[i] = 1;
   }
   

   • 外层循环j遍历到sqrt(246913)（用j < 246913/j是为了避免整数溢出，等价于j*j < 246913）
   • 若arr[j]==1，说明j已被标记为非素数，直接跳过
   • 内层循环从j*j开始，每次加j，把j的所有倍数标记为1（非素数）。其中if (i%j==0)是冗余代码——i是j的倍数，必然满足该条件，不影响核心逻辑

3. 统计目标区间素数

   int cnt = 0;
   for (i = N + 1; i <= N * 2; i++)
       if (arr[i] == 0)
           cnt++;
   printf("%d", cnt);
   

   • 遍历区间(N, 2N]（从N+1到2N），统计标记为0（素数）的数字个数并打印
   • 示例：func(7)统计8-14的素数（11、13），输出2；func(4)统计5-8的素数（5、7），输出2

4. main函数调用
   依次传入不同N值，输出对应区间的素数个数

新手读算法代码的实用技巧 #

• 从输出倒推核心目标：先看代码最终输出的内容，比如这段代码打印的是区间内素数的计数，再反向梳理逻辑
• 明确变量/数组的含义：优先搞清楚数组下标、变量值代表的实际意义，比如arr[x]的x是数字，值是素数标记，这是理解代码的核心
• 拆分代码块：把代码拆成「初始化」「预处理」「计算/输出」模块，逐个分析，避免一次性看完整段代码的混乱
• 代入小例子跑流程：拿简单输入（比如func(7)）手动走一遍代码，标记数组的变化，快速理解逻辑
• 关联常见算法模型：看到「标记倍数」「筛选素数」的逻辑，直接关联埃氏筛这类经典算法，不用从头推导
• 忽略冗余代码：遇到明显多余的代码（比如这段里的if (i%j==0)），先跳过抓核心逻辑，之后再回头分析冗余部分

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