如何用C实现埃拉托色尼筛法算法？

Question

在我的书中，Stephen G. Kochan 的《C 语言编程》（第四版）中，我有一个实现埃拉托斯特尼筛法算法的任务，如下所示：

\n

显示 1 到 n = 150 之间的所有素数

\n

\n
• 步骤1：定义一个整数数组P。将所有元素Pi设置为0，
\n
• \n

       2 <= i <= n.\n

  \n
\n
• 步骤 2：将 i 设置为 2。
\n
• 步骤3：如果i > n，算法终止。
\n
• 步骤 4：如果 Pi 为 0，则 i 为素数。
\n
• 步骤5：对于j的所有正整数值，使得ixj \xe2\x89\xa4 n，
\n
• \n

       set <sub>Pixj</sub> to 1.\n Step 6: Add 1 to i and go to step 3.\n

  \n
\n

\n

我理解广泛的概念，但很难理解算法中的步骤以及每个步骤的目的。

\n

问题：

\n

\n

1. 在步骤1中，将所有元素p[i]设置为0的目的是什么？数组元素不需要从 0 到 150 开始吗​​？

   \n
\n

2. 在步骤 4 中，这是否意味着 i 的倍数得到值 0，并且如果任何非零的值将是素数？本质上，它会将 i 的所有倍数转换为 0（合数）并保留所有素数？

   \n
\n

3. 第 5 步让我很困惑，我不知道如何就此形成一个连贯的问题。像这样的下标是什么意思_Pixj？另外，步骤 4 的逻辑没有意义，如果可能的话，我需要更通俗易懂的术语。（只要有一个提示就可以了，这样我就可以自己得到）

   \n
\n

\n

仅供参考，我是学习计算机科学和编程基础知识的初学者，因此我们将不胜感激！上面的练习来自第 6 章：数组。谢谢你！

\n

我还没有尝试过代码，我需要先了解算法步骤。

\n

Answer 1

\n

在步骤1中，将所有元素p[i]设置为0的目的是什么？数组元素不需要从 0 到 150 开始吗​​？

\n

\n

数组P用于记录一个整数是否已知为非素数。每个元素 P _i都初始化为零，以表示算法最初不知道i是否为非素数。

\n

\n

在步骤 4 中，这是否意味着 i 的倍数得到值 0，并且如果任何非零的值将是素数？[本质上]，它将把 i 的所有倍数转换为 0（合数）并保留所有素数？

\n

\n

第 4 步描述得不好。当算法到达步骤 4 时，已经执行了足够的工作，如果 P _i为零，则i必须是素数。在步骤 4 中，算法旨在通过某种方式报告这一事实，例如将i写入标准输出。

\n

\n

第 5 步让我很困惑，我不知道如何就此形成一个连贯的问题。Pixj 这样的下标是什么意思？另外，步骤 4 的逻辑没有意义，如果可能的话，我需要更通俗易懂的术语。（只要有一个提示就可以了，这样我就可以自己得到）

\n

\n

\xe2\x80\x9cPixj\xe2\x80\x9d 表示 P _{i \xc3\x97 j}。在步骤 5 中，算法有一个i并在j上迭代循环。在该循环的每次迭代中，代码应计算乘积t = i \xc3\x97 j并将 P _t设置为 1，表示t已知为非素数（因为它是i和j的乘积） ）。

\n