使用筛选法生成素数表及回溯法解决N皇后问题

"筛选法创建素数表-搜索算法 ACM" 在给定的资源中，主要涉及了两个关键概念：筛选法创建素数表和搜索算法。筛选法用于生成素数表，而搜索算法则是一种解决特定问题的策略，这里特别提到了回溯法。 首先，我们来看筛选法，也称为埃拉托斯特尼筛法，这是创建素数表的一种经典算法。在提供的代码段中，`prime` 这个过程展示了埃拉托斯特尼筛法的基本步骤。它首先初始化一个布尔数组 `p`，大小为 `n` 的两倍，用于标记数字是否为素数。数组的索引代表数字，`p[i] = true` 表示数字 `i` 是素数，反之 `p[i] = false` 表示不是。然后，从2开始遍历数组，对于每个素数 `i`，将它的所有倍数标记为非素数，直到超过数组的范围。这个过程有效地筛掉了所有合数，留下的 `p[i] = true` 的位置对应的数字就是素数。 接着，我们讨论搜索算法。在这个资源中，搜索算法特指回溯法。回溯法是一种通过尝试解决问题的不同解决方案，并在发现当前路径无法解决问题时返回上一步，尝试其他可能性的方法。它通常用于解决约束满足问题，例如八皇后问题。在八皇后问题中，目标是在一个 n × n 的棋盘上放置 n 个皇后，使得任何两个皇后都不在同一行、同一列或同一对角线上。资源中提到的 `try` 函数就是一个典型的回溯搜索过程，它尝试放置第 k 个皇后，如果找到了可行的放置方式，就递归地尝试放置下一个皇后。如果发现当前皇后的位置不合法，即与已放置的皇后冲突，那么就回溯到上一个皇后，尝试新的列来放置。 `place` 函数则是用来检查第 k 个皇后能否安全地放在第 i 列，它会遍历已经放置的前 k-1 个皇后，如果发现有冲突（在同一行、同一列或同一对角线上），则返回 `false`，表示不能放置；否则返回 `true`，表示可以放置。 最后，`print` 函数用于输出找到的解，也就是一个有效的皇后放置方案。在搜索过程中，每次找到一个解，就会调用 `print` 函数增加计数器并显示当前解。 总结来说，这个资源涵盖了两个核心概念：筛选法创建素数表，用于找出一定范围内的所有素数；以及回溯法作为搜索策略，解决约束优化问题，如八皇后问题。这两个算法在计算机科学和编程竞赛（如 ACM 比赛）中都是非常基础且重要的工具。