埃拉托斯特尼筛法，厄拉多塞筛算法，C#实现

埃拉托斯特尼筛法，厄拉多塞筛算法

这个 很多地方的定义不一样。
虽然名字相同，但是具体的定义还是有差距。

有的地方描述的是：
厄拉多塞筛算法(Eratosthenes Sieve)是一种求素数的方法，由古希腊数学家厄拉多塞提出。它的原理是，给定一个数n，从2开始依次将根号n以内的素数的倍数标记为合数，标记完成后，剩余未被标记的数为素数(从2开始)。如此可省去检查每个数的步骤，使筛选素数的过程更加简单。厄拉多塞筛算法具体步骤如下:
(1)读取输入的数n，将2至n的所有整数记录在表中:
(2)从2开始，划去表中所有2的倍数;
(3)由小到大寻找表中下一个未被划去的整数，再划去表中所有该整数的倍数;
(4)重复第(3)步，直到找到的整数大于根号n为止;
(5)表中所有未被划去的整数均为素数。

差距就是有的是根号N，有的是N。

下面实现的是没有根号的版本。

C# 实现

            var ll = SieveOfEratosthenes(10);ll.ForEach(e => { Console.WriteLine(e); });/// <summary>/// 埃拉托斯特尼筛法/// </summary>/// <param name="maxValue">最大值</param>/// <returns>符合条件的素数集合</returns>private static List<int> SieveOfEratosthenes(int maxValue){List<bool> bl_list = new List<bool>();List<int> int_list = new List<int>();// 初始化 bl_list，默认值为 false（表示是质数）for (int i = 0; i < maxValue + 1; i++){bl_list.Add(false);}// 0 和 1 不是质数bl_list[0] = true;bl_list[1] = true;// 开始筛选for (int i = 2; i * i <= maxValue; i++){if (!bl_list[i]){for (int j = i * i; j <= maxValue; j += i){bl_list[j] = true; // 标记为非质数}}}// 收集所有质数for (int i = 2; i <= maxValue; i++){if (!bl_list[i]){int_list.Add(i);}}// 打印结果（可选）for (int i = 0; i < bl_list.Count; i++){Console.WriteLine($"i={i}：" + bl_list[i]);}return int_list;}

输出：

i=0：True
i=1：True
i=2：False
i=3：False
i=4：True
i=5：False
i=6：True
i=7：False
i=8：True
i=9：True
i=10：True
2
3
5
7

C++实现

 #include <iostream>
#include <vector>std::vector<int> SieveOfEratosthenes(int maxValue) {std::vector<bool> bl_list(maxValue + 1, false); // 初始化 bl_list，默认值为 false（表示是质数）std::vector<int> int_list;// 0 和 1 不是质数bl_list[0] = true;bl_list[1] = true;// 开始筛选for (int i = 2; i * i <= maxValue; i++) {if (!bl_list[i]) {for (int j = i * i; j <= maxValue; j += i) {bl_list[j] = true; // 标记为非质数}}}// 收集所有质数for (int i = 2; i <= maxValue; i++) {if (!bl_list[i]) {int_list.push_back(i);}}// 打印结果（可选）for (int i = 0; i < bl_list.size(); i++) {std::cout << "i=" << i << "：" << bl_list[i] << std::endl;}return int_list;
}int main() {int maxValue = 10; //查找10以内的 std::vector<int> primes = SieveOfEratosthenes(maxValue);std::cout << "Prime numbers up to " << maxValue << " are: ";for (int prime : primes) {std::cout << prime << " ";}std::cout << std::endl;return 0;
}

输出：

i=0：1
i=1：1
i=2：0
i=3：0
i=4：1
i=5：0
i=6：1
i=7：0
i=8：1
i=9：1
i=10：1
Prime numbers up to 10 are: 2 3 5 7