赞
踩
这个 很多地方的定义不一样。
虽然名字相同,但是具体的定义还是有差距。
有的地方描述的是:
厄拉多塞筛算法(Eratosthenes Sieve)是一种求素数的方法,由古希腊数学家厄拉多塞提出。它的原理是,给定一个数n,从2开始依次将根号n以内的素数的倍数标记为合数,标记完成后,剩余未被标记的数为素数(从2开始)。如此可省去检查每个数的步骤,使筛选素数的过程更加简单。厄拉多塞筛算法具体步骤如下:
(1)读取输入的数n,将2至n的所有整数记录在表中:
(2)从2开始,划去表中所有2的倍数;
(3)由小到大寻找表中下一个未被划去的整数,再划去表中所有该整数的倍数;
(4)重复第(3)步,直到找到的整数大于根号n为止;
(5)表中所有未被划去的整数均为素数。
差距就是有的是根号N,有的是N。
下面实现的是没有根号的版本。
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
#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
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。