导读 在数学的世界里，素数（只能被1和自身整除的大于1的自然数）是构建数字王国的基础之一。而如何高效地找到这些“孤独的星星”呢？答案就是—...
在数学的世界里，素数（只能被1和自身整除的大于1的自然数）是构建数字王国的基础之一。而如何高效地找到这些“孤独的星星”呢？答案就是——线性筛法！✨
首先，我们明确线性筛法的核心思想：通过一个数组标记所有非素数，同时利用已知的素数来筛选后续数字。这种方法的时间复杂度接近O(n)，远优于传统的试除法。🔍
实现步骤如下：
1️⃣ 初始化一个布尔数组`is_prime`，将所有位置设为`True`。
2️⃣ 从2开始遍历，若当前数字未被标记，则它是素数，并将其倍数全部标记为非素数。
3️⃣ 遍历完成后，未被标记的索引即为素数。
例如，在寻找1~10的素数时，最终结果为[2, 3, 5, 7]。💡
线性筛法不仅效率高，还易于实现，是算法竞赛中的必备技能。掌握它，你也能轻松驾驭素数的海洋！🌊
算法 数学 编程