在C语言中实现埃拉托斯特尼筛法的算法步骤疑问

先明确核心前提：这个数组P不是用来存储0~150这些数字的，它是一个标记数组——数组的下标i就代表数字i，数组里的0或1是对这个数字的状态标记：

• P[i] = 0：数字i是「素数候选人」（未被标记为合数）
• P[i] = 1：数字i是合数（已被筛除）

问题1：步骤1中，将所有P[i]设为0的目的是什么？数组元素初始值难道不应该是0到150吗？ #

这个数组的作用不是存数字，而是通过下标关联数字，用元素值做标记。

• 初始把2~150对应的P[i]设为0，是默认所有数都是素数候选人，后续只需要把合数标记成1就行，不用改动素数的状态（保持0即可）。
• 要是存0~150的数字，后续筛除合数还要一个个查找、删除，远不如用下标对应数字、标记值区分状态来得高效。

问题2：步骤4是否表示i的倍数会被设为0，非零值对应的数是素数？本质是将所有合数转为0，留下素数？ #

完全搞反了标记逻辑，重新理清楚：

• P[i] = 0：代表数字i没被任何更小的素数标记为合数，所以它本身就是素数。
• P[i] = 1：代表数字i是合数，已经被筛除了。
  步骤4的逻辑是：当遍历到i时，如果P[i]还是0，说明没有比i小的素数能整除它（不然早就被标记成1了），那i肯定是素数。而步骤5是把i的所有倍数标记成1，因为这些数都是合数（能被i整除）。

问题3：步骤5完全令我困惑：下标P[i×j]是什么意思？另外步骤4的逻辑我也不太明白，能否用更通俗的语言给出提示？ #

关于P[i×j]的含义 #

i是当前遍历到的数，j是从2开始的正整数（j=2、3、4...），i×j就是i的倍数。比如当i=2时，j取2得到4，取3得到6，取4得到8...这些数都是2的倍数，肯定是合数，所以把它们对应的数组位置（P[4]、P[6]、P[8]...）设为1，标记成合数。

通俗版步骤逻辑 #

把整个过程想象成给1~150的数发「清白卡」筛合数：

1. 先给2~150的数每人发一张清白卡（标记为0），默认都是素数候选人。
2. 从2开始挨个检查：
   • 拿到2时，它的清白卡还在（P[2]=0），说明没人说它是合数，那它就是素数。接着把所有2的倍数（4、6、8...）的清白卡收走（标记为1），因为这些数能被2整除，肯定是合数。
   • 检查3时，清白卡还在，说明它没被之前的素数（只有2）筛掉，所以3是素数。接着收走3的倍数（6、9、12...）的清白卡。
   • 检查4时，清白卡已经被收走了（P[4]=1），直接跳过。
   • 检查5时，清白卡还在，是素数，收走5的倍数的清白卡。
3. 一直检查到150，最后手里还拿着清白卡（P[i]=0）的数，就是所有素数。

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