桑达拉玛筛

网络中的Sundarama筛网以大量简短的背景信息为代表。 尽管如此，我还是决定说自己在数论算法研究之初要读什么。

Sundarama筛子是生成质数的三种最著名的方法之一。 现在，由于计算复杂性低，通常将其视为奇特的：O（N（logN））。 但是，渐近是渐近的，实际上，在32位筛选范围内，例如，Atkin仅通过精心优化就可以替代Sundaram。

在互联网上流通的Atkin筛子的实现无论在时间上还是在内存效率上都没有超过Sundaram筛子。 因此，Sundaram方法可以用作具有更高级算法的实验的辅助工具。

Sundarama筛子在给定的自然数3≤n≤N的给定范围内找到所有素数，从而“筛选出”组分。 不失一般性，N的值可以认为是奇数。 如果N是偶数，则可以保证它是合成的，并且可以通过将上边界的值减一来将其从筛分范围中排除。

该算法基于以下事实。 任何奇数复合数n都可以表示为两个大于1的自然奇数的乘积：

（1） n =（2 * i +1）*（2 * j +1），

其中i和j是自然数（零不是自然数）。 无法想象这种形式的质数n，因为否则将意味着n除他自己和一个之外还具有其他除数。

我们以2 * m + 1的形式编写奇数n，将其替换为（1），然后获得m的表达式：

（2） m = 2 * i * j + i + j。

这种转变直接导致了Sundaram筛网的想法。

为了从给定的间隔中去除合成数字，您应该使用一个数组，其中索引为m的元素代表数字2 * m +1。在组织完变量i和j的值的枚举后，我们将通过公式（2）计算索引m，数组元素设置标记“复合数”。 枚举完成后，将标记该范围内的所有复合数字，并且可以通过不带标记来选择质数。

仍然需要澄清技术细节。

根据前面的推理，为了表示筛分范围N的上（奇数）边界，索引m假定其最大值mmax =（N-1）/ 2。 这确定了所需的数组大小。

我们将在两个周期中枚举i和j的值：一个用于枚举i值的外循环，以及一个嵌套的j值的内循环。

外部循环计数器的初始值为i =1。考虑到表达式（2）中变量i和j的出现完全对称，为避免重复重复计算，内部循环应从值j = i开始。

查找外部环路计数器imax≥i的最大值。 如果范围N的边界是一个奇数，则对于i = imax，必须使用其参数j = imax的值至少执行一次内部循环以删除N，表达式（2）将取其最大值：

mmax = 2 * imax * imax + imax + imax，
imax ^ 2 + imax-mmax / 2 = 0。

求解这个二次方程式，我们得到： imax =（√（2 * mmax + 1）-1）/ 2 =（√N-1）/ 2。
从不等式中找到内部循环jmax≥j的计数器限制
mmax≥2 * i * j + i + j ，则得到： jmax =（mmax-i）/（2 * i + 1）。

上限的值应四舍五入到最接近的整数，舍去小数部分。

以下是实现上述方法的非常简单的C＃Sundaram类的清单。

using System; using System.Collections; namespace CSh_Sundaram { public class Sundaram { public double dt; //   () private long t1; //   private long t2; //   private uint limit; //     private int arrlength; //   private BitArray Prim; //    private int counter; public Sundaram(uint _limit) { limit = _limit; if (limit % 2 == 0) limit -= 1; arrlength = (int)(limit / 2); Prim = new BitArray(arrlength); t1 = DateTime.Now.Ticks; Sieve(); //  t2 = DateTime.Now.Ticks; dt = (double)(t2 - t1) / 10000000D; counter = -1; } public uint NextPrime { get { while (counter < arrlength - 1) { counter++; if (!Prim[counter]) return (uint)(2 * counter + 3); } return 0; } } private void Sieve() { int imax = ((int)Math.Sqrt(limit) - 1) / 2; for (int i = 1; i <= imax; i++) { int jmax = (arrlength - i) / (2 * i + 1); for (int j = i; j <= jmax; j++) { Prim[2 * i * j + i + j - 1] = true; } } } } } 

作为创建Sundaram类型的对象时的参数，指示了筛分范围的上限。 为了进行筛选，该类使用BitArray类型的数组。 这样可以增加运行时间，但可以覆盖uint类型的整个32位范围。 从类构造函数访问Sieve（）方法时执行筛选。 完成后，dt字段将包含以秒为单位的Sieve执行时间。

当访问NextPrime属性时，从3开始按顺序升序返回素数。 用完该范围内的所有简单变量后，将返回值0。