为何此埃拉托斯特尼筛法采用prime[n/2]等形式？求解析

这个实现是针对奇数的空间优化版筛法，核心思路是跳过所有偶数（除了2本身），从而把内存占用砍半，同时减少循环次数，这就是它比常规筛法高效的原因。下面拆解你提到的两个关键点：

1. 为什么用prime[n/2]初始化数组？ #

常规筛法会为每个从2到n的数分配一个标记位，但除了2之外，所有偶数都不可能是素数，完全不需要浪费空间去标记。我们只需要关注奇数：从3到n的奇数总数大约是n/2（当n为偶数时正好是n/2；n为奇数时是(n+1)/2，取n/2是简化边界处理的写法）。用大小为n/2的数组，每个元素对应一个奇数，直接把内存占用减少了50%。

2. 为什么多处使用prime[i/2]、prime[j/2]？ #

这里的i和j都是奇数，i/2（整数除法）的结果就是该奇数在数组中的索引。举个例子：

• 奇数3对应的索引是3//2=1，所以prime[1]用来标记3是否为素数；
• 奇数5对应的索引是5//2=2，对应prime[2]；
• 筛除素数p的倍数时，我们只需要处理奇数倍数（比如p=3，倍数是9、15、21...），这些数的索引就是9//2=4、15//2=7，所以用prime[j//2]来标记这些数为非素数。

这种映射方式把奇数和数组索引一一对应，既实现了空间优化，又不影响筛法的核心逻辑——标记非素数。

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