讨论关于埃氏筛存在的合理性
最近在读一些闲书的时候又遇到了这个神奇的东西，
素数，即只包含其本身因子与1因子的数。
当然，对于这个东西，我们更通常使用的说法是：
只能被1和其本身整除的数。
其实都差不多，这个东西应该是在小学甚至幼儿园就可能遇到的东西。
与素数相对应的数是合数，也就是不止包含其本身与1两个因子。
还有两个比较特殊的数是“1”和“0”，我曾学过的数学系统对这两个数的定义是：既不是质数（也就是素数）也不是合数，至于其他人学过的系统我也听说过将1算在素数中的，但在此不讨论这个问题。
所以我接下来的讨论不包括对“1”和“0”的讨论。
我个人对数学证明的整体的学习是很欠缺的，所以我会尽量用更逻辑一点的语言叙述而不是用数学符号（毕竟我是在看不懂那些用纯数学概念证明的文章）
我突然发现，只要你读到偏理偏工的书，不论是计算机类的导论丛书，还是数学、物理、甚至是化学、机械工程等等方面的导论丛书，在接触到用纯数字证明时，都有可能碰见这个东西。
我最近读的闲书是关于算法的书目，里面提到了对树型、图型、不规则集合等ADT的描述算法的优化型都有可能用到素数，比如对散列表的优化方案中的“再散列”“可扩散列”等等都会出现依靠素数进行高效优化的步骤，甚至于密码的加解密，数据的复序列化等都可能用到。
对于素数这个领域，其应用面之广是我所不能征及的，且讨论其可应用性也不是我这个领域所能描述的。所以我们只讨论一下这个领域最浅层但最核心的东西，那就是求素数。
如果你或者因为兴趣接触过计算机编程（比如我），或者因为专业要求学习过数据结构与算法，那在学习循环，或者是算法实现时应该都接触过素数求法，最常用也最大众化的一般是两种。
第一种是定义法，因为素数只包含1与其本身两个，所以对于一个给定数X，我只要用这个X依次去整除区间[2,X-1]的所有整数，如果被其中某一个数整除，那X就不是素数，反之就是。
第二种不能说是一种方法，而是一个类别，是对第一种的优化，简称优化定义法，比如说根据定义除了2这个数字之外，所有的偶数一定都不是素数（因为X会有2这个因数），所以在给定区间内抛开素数，对剩余部分进行定义法；再比如我们不去考虑[2,X-1]的区间，仅考虑其的给定区间部分，比如说定义法的给定区间只考虑[2,(x)^(1/2)] (ps：我实在不知道该怎么画出根号。。。) 至于这个区间的合理性，也就是为什么可以做到循环至根号x就可以这一点，我不记得了，但这是一个很简单的数学推理，所以忽略。
至于为什么“明明第一种就能解决任何区间的找素数问题，为什么会存在第二种”出现这种问题，答案就一个字，优化，计算机的算力资源是有限的，但第一种看似通用的算法实际上在你想要查找的区间很大时，他要用到的时间也是难以想象的。
这里本来应该引用一下时间复杂度的概念，但这个东西并不会实际影响我们的证明，所以各位如果有兴趣接触到这一方面内容的，可以自行百度。
好了，说了这么多，其实就是为了说明，埃氏筛能够出现的第一个要点就是为了提高查找素数的效率，节省计算机算力资源。
前两天正好也碰到了有人提到埃氏筛这个东西，所以我们今天就主要讨论一下这个东西。（
接下来我们开始说正题，也就是埃氏筛的合理性。
首先，埃氏筛是一种高效查找指定区间内素数的算法，对于其运行的数学描述我就不多赘述，喜欢的可以自行百度。
我会尽量精准的描述这一算法的运行过程。
我们明确两个定理：
第一，在自然数中，除0与1之外的任何数不是素数就是合数。
第二，任何一个合数都是某一素数的倍数。
（ps：我不知道这两个需不需要证明，但我感觉应该是不需要的。）
接下来是埃氏筛的核心：
对于给定区间内的自然数，如果想要得到该区间内的所有素数，那么就要删除所有素数因子的倍数。
这是比较笼统的说法，没有加上不大于根号n的限制条件，也没有纠结对算法的更精细化。
埃氏筛其实是很好理解的一种算法，为什么这么说呢，只要你再看一眼我们明确的两个定理，其实这种算法的合理性就是显而易见的了，比如说，在给定区间[a,b]内，其内部存在的数要么是素数要么是合数（第二个定理），那么删除掉所有的合数，剩下的肯定就是素数。
把2选定为素数颜色红色，再把2的倍数标为绿，去掉，再去掉3的倍数蓝色，5的倍数黄色，7的倍数紫色，剩下的就是素数，我全部涂成红色了。1不是质数也不是合数，就不管。
很简单，对吧？
但如果你和我一样是一个喜欢钻牛角尖的人，那么就会冒出一个小问号，“这么做为什么是合理的呢？”换句话说，为什么我把这个范围内小于范围的素数因子的倍数都删除，就能得到所有的素数呢？会不会存在反例呢？
我相信或许会有人困惑于这个反例，不知道该叙述，其实我们可以把“删除素数因子倍数”的过程称为吞噬（或者筛选），寻找素数的过程称为再生，而这个定理所体现的其实就是吞噬的程度将远大于再生的程度。
什么意思呢？ 大概就是说，我们通过吞噬(或者是说筛选）后会得到一个新的集合，埃氏筛则是说明在这个集合里一定存在我们想要找的这个素数（又或者是一个新的素数，也就是这个素数生成的一瞬间就被包裹在集合中）。
如果我们把吞噬与再生当作两个时不时并发的并行计算机，那么吞噬运行的速度远高于再生的速度，这是证明埃氏筛合理性的核心。
对于反证法的证明就不多说了，毕竟反证法非常容易理解。各位可以试着反证一下。
我们从计算机运行的角度进行前进式证明。
假设给定区间[a,b]，寻找一个素数X,
对于自然数区间，该数X一定有两个邻接区间，U-与U+，我们规定这两个区间内只存在合数，并且尽量贴合X（为了证明方便，即便某一方里存在素数，我们通过缩小区间也是可以以此证明的）
我们只要能够证明U-与U+两个区间可以完全被小于X的素数因子的倍数“吞噬掉”或者说完全被“筛掉”，那么就说明该算法是合理的。
U-这个部分其实比较简单，这个区间右界就小于X，那么里边的所有合数都要小于X。
根据明确定理二，所有的合数都是某一素数的倍数，在这个区间内所有合数都会是小于X的素数因子的倍数，通过吞噬是可以完全吃掉这一部分。（这里还有一个理念，那就是递归，这一部分是类似于递归的，因为吞噬掉这部分的基础是小于X的素数因子，那么这些因子又会是比其更小的素数因子的基础进行吞噬，直到追溯至“2”与“3”两个数字为止）
U+这个部分，首先我们已经直到其内部小于X的素数因子的倍数已经删除干净了，那么接下来只要能说明大于等于X素数因子的倍数被吞噬就好了。
U+这个部分最大回到多少呢？ 最大应该是到2X-1，到不了2X，因为2X肯定不是素数，在找寻大于X的素数时根据递推原则，2X会是大于X的U-，也会被吞噬。
那么在U+到2X-1内是否会存在不能吞噬的部分呢？这样看来是不行的，毕竟2X-1本身是小于X的倍数（2X），换句话说，充其量其本身也只会是小于X的素数因子的倍数，而如此便能将对U-的讨论推广到U+之上。
我们再把这个区间与X推广至任意数。
也就是说对于任意素数，其周围的合数都会完全的被“吞噬掉”，那么该素数就一定可以被找到。
又因为素数被完全吞噬，那么也不会有某个合数是“漏网之鱼”。
如此，U-与U+都会被小于X的倍数吞噬掉，则说明在给定区间内寻找素数X是可行的，且不会被漏掉（因为吞噬的很干净）。
埃氏筛的合理性也就得证。
其实这是并不复杂，却很愚笨的证明方式，在现存的文献与论文中，纯数学推理与逻辑推理证明这个东西的数不胜数，比我所想到的这种方法要更严谨的更简约的也有很多。
但我为什么还要如此的、近乎直白的叙述问题呢，因为我发现，大多数的教科书更喜欢告诉你用的合理性，但不会告诉你其存在的合理性。
换句话说，他们会告诉你：在写算法时只要剔除掉已求素数以及求完的素数的倍数（从2，3开始），剩下的就是素数。
但他们不会多说一句这种算法存在的合理性是因为“任一合数是小于其本身某素数因子的倍数”这么一句简单的东西。
或许是一瞬间就明白的人认为这种东西不用点名，也或许没明白的认为这种东西就应该这样，
也只有像我们这种喜欢钻牛角尖的人愿意啰嗦两句吧。
以前在讨论的时候有人说填鸭式教育会失去知识的敏捷性，或许就会出现这样的情况吧。
我的证明并没有技术含量，所以可能并不存在逻辑上的完全的自恰与严谨（可能有某种情况是我没有想到的），如果各位对于这个东西真的感兴趣，对于计算机领域与算法领域有一定涉足的想法，请去看专门的书籍与讨论文献。
虽然我也只是对这方面在这段时间产生了兴趣罢了。。。。。。
据说现在不提倡那种资源帖了，就不贴了，想要资源的可以学习纵云梯直接google（琉璃神社在谷歌可以直接查到唉，我也才知道。。。。）
-
0是不是空集这个问题不是我们应该讨论的，因为对于我们的讨论并没有任何帮助，但是0总是需要去讨论的，这是很多数学文献中着重提到过的东西，0本身就是一个非常神奇的东西。
皮蒂亚
0不是素数，0就是空集，什么都没有，没有讨论的意义。1是素数不是素数都可以，这个要看情况，怎么方便怎么来，只要是严格定义的。求素数有很多算法，而且有不少素数通项公式。然而并不存在高效的算素数的算法，可 ...
甚至有几本书是专门讨论0的意义，其本身意义决不可忽略。
不论是纯数学领域还是计算机领域都会存在高效与简洁一说，高效的算法对标的是低劣的算法。
比如说在数学逻辑领域，对于二等范式的优化一定是要借助一等式的，这就是高效的、简洁的体现，如果用三等逆推二等，这就有些得不偿失了。
再比如说算法领域
这两个概念涉及到了我上边提到过的时间复杂度的讨论，也就是O、o、π的近似值表示法，这个东西要从头理解是比较困难的，我只讲大概意义，
我们常用的大O表示法是指对于某种运算或者算法估计时提出的上界函数，这种上界是可知但不一定可达到的。
比如说，我们用定义法求素数，加入要寻找[1,N]这n个数中的素数，根据定义法，每个数X都要求其与[2,X-1]区间内每个整数的整除，我们规定每次整除要一个单位时间，那么数X的判断就需要大约(X-3)个单位，我们姑且当作是X个单位（因为是近似函数，方便计算），那么对于[1,N]这其中的n个数，就需要N*X个单位时间。
标准大O法要计算运算过程的最优解与最差解求平均值，但往往为了找到最高限影响因子我们会忽略最高值只看最差解，很明显，N*X的最差解是N的平方。
换句话说，这个算法会近似为N的平方个单位时间的运算，如果N取足够大，计算机的算力资源将会完全的不够。
而第二种优化法大约可以达到1/2N^2的单位时间，在极差时可能也会接近N的平方。
再看埃氏筛的算法，这种算法可是top-down也可以是bottom-up的，其算法近似的公式我忘了，但对于[1,N]的n个数，任意一个数的素数判定都会造成大约以2为底N的对数次（这很容易理解，因为对于一个数X，如果数X之前的素数被找到了，那么找到X的速度将会更快，毕竟吞噬速度远远大于再生，其次吞噬的过程与我之前提到的算法领域的递归思想是相似的，对于泛型递归算法的近似值是递归树的高度，大约是log2N），那么对于n个数的大约值就是N*logN（以2为底），根据欧拉推论，其也可以约为N*log1.44（又或者是什么什么，我忘了），近似于工程数e。
很明显，NlogN的函数要比N^2的幅度更低，效率更高。
而至于之后欧拉在此基础上推导出的更高效的算法，那就是数学领域的优化了。
★ -
素数的通项公式如果近几年数学领域没有突破，那应当是没有出现的，即便是欧拉（还是黎曼？还是那个历史老师？）退出来的非常近似的公式，其实也不能完全的概括所有素数，仅能做必要条件，也就是说不具备充要，没有实际用途。
皮蒂亚
星辰乄 0是不是空集这个问题不是我们应该讨论的，因为对于我们的讨论并没有任何帮助，但是0总是需要去讨论的，这是很多数学文献中着重提到过的东西，0本身就是一个非常神奇的东西。 甚至有几本书是专门讨 ...
其次，因为我的讨论没有涉及到效率问题所以有些细节问题我没有明说，但如果你提到了通项公式与递推的问题，那对效率问题的考虑就不能简单地概括为线性（通项）一定比非线性（递推）的效率高了。
这里涉及到了计算机领域的知识，我还是再讲个大概。
首先，计算机最底层运算依托于二进制位运算，如果不容易理解或者说百度后也不好理解，可以简单地理解为对某个数进行乘以2或者除以2，无论是加减乘除都会在计算机内部转化为加法器的加运算，然后变成底层的位运算，我们一般只讨论到这个地步，而接下来的逻辑门与我们的讨论并无关联。（这在如今不是一定的了，因为确实出现了特例于位运算的计算机）
位运算的优势在于运算效率高，速度快，这一点在每一门编译语言中都有体现。
我为什么要提到这个问题呢，因为线性与非线性的运算效率取决于两个层面，第一个是逻辑层面，也就是表现形式上是否更优于运算，很显然，线性更优越。
第二个是运算层面，这一点会是线性的硬伤，虽然我们一直宣称O（1）也就是线性运算优于非线性，但这是超脱理想，有足够的实验表示，线性运算在计算机中也会呈现非线性特性，即便这个特异点会非常的大。
但找素数本身就是一个近乎找极限的过程，那么这个特异点将会不断出现。
换句话说，不论对于计算机还是人来说，要算1234554321乘1234554321可能需要一点时间，但终归可以得到，甚至对如今的计算机来说可能是一瞬间的事情。但如果是1234554321的1234554321次方，显而易见的（对于这种大数乘法也是存在相关数学公式计算的，但这一步的ADT模拟将会进一步增加线性公式的效率，或许会从O(1)变成O（logN），甚至是O（N）甚至是其他变化）。
我们再考虑非线性的递推公式，我们曾经证明吞噬速度是远大于再生速度的，那么我们有理由相信，对于非线性递推的描述曲线中，振幅应当小于等于线性的振幅。
当然这并不能完全的证明，在一定程度上非线性可能会优于线性，因为这违背其物理概念。
Willans在1964年提出的算法复杂度应该是近似于O(2^N)而不是O(2^(3*n)），因为后者并不直观，而且在数学中大O应当表现为一个上界函数，且有相对应的符号（大概）。
至于说zeta函数之类的，这个不是我的领域了，毕竟我也只是最近对这部分产生了兴趣。
★ -
-
啊，我突然发现刚才说的有一个地方有些跳跃，说了计算机和运算但没说关系。
皮蒂亚
还有，欧拉那个不是素数算法，就是一个zeta函数的等价公式，可以用筛法推，长这样子(p是素数)：
其实概括来说就是一句话，计算机运算是存在局限的，并且局限很大。ps：这不能再展开了，在展开就更多了，相关知识可以查询内存、cache、io缓存等概念。
总之，计算机运算存在局限，致使其对于单一运算的效率虽然普遍很高，但又是也会很低，这就造成了它如同人一般的尴尬个性:运算量简单，我算的快，运算量复杂，我算的也不快。只不过计算机的这个局限上限很高，所以一般算法不能体现。
而非线性递推是前进式算法（预瞻式算法），一种堆叠算法，算的越多，算的越快（主观上的，相比于线性运算。因为堆叠上限是logN所以实际并没有更快多少）。
啊，还有一点，我说的线性与非线性并不是代数那种中的线性，是为了区分O(1)与其他复杂度，算法这个方面O(1)称为线性运算，我是这个意思。
★ -
我非常认可“对于相关事物的描述以数学更严谨”这样的观点，数学逻辑的证明会令这个东西更加的直观与清晰，且不会存在黑箱。
皮蒂亚
还有，欧拉那个不是素数算法，就是一个zeta函数的等价公式，可以用筛法推，长这样子(p是素数)：
但也很遗憾，非常的数学描述都是停留在理论层面，而从理论层面到应用层面的转化过程往往会令效率低劣化，甚至低劣化到令人难以想象的程度。
其实数学本身就是优化的东西，其本身存在就是一种优化。可以概括地说，如今每一种算法，数据模型，结构优化等 效率优化都离不开数学描述与优化这一步。
至于说在数学层面的优化，就像我前一句说的，很重要而且核心，不好的数学公式劣化为不好的数据模型，对算力资源是灾难性的，而一个好的数学公式劣化的模型的效率是非常可观，且节省不小数目的算力。
数学这个领域对我来说过于难以企及，我确实没有什么资格去对其指点一二的。
★ -
-
皮蒂亚 星辰乄 素数的通项公式如果近几年数学领域没有突破，那应当是没有出现的，即便是欧拉（还是黎曼？还是那个历史老师？）退出来的非常近似的公式，其实也不能完全的概括所有素数，仅能做必要条件，也就是说不具 ...
我后边有所介绍，其实我借用的线性与非线性并不完全是数论里为了描述数据浮动的东西，是为了区分O(1)与其他复杂度，比如O(N)、O（logN）、O(N^N)等等。
在一般情况下我们认为O(1)是线性实现，是最快的，其实实际的意义便是一个常函数，比如说一次加运算，一次乘运算等等，再比如说小计算量的代数运算，解方程等等，这种能通过一次运算得到结果的，一般认为是O(1)的复杂度（忽略内部复杂的底层的运算过程），也认为是线性的，因为相对于O(1)这样的常量估值，O(N)、O（logN）、O(N^N)都可能存在相互扰动。比如说我们虽然说一个算法近似于O(N)，但实际上是近似成N的一次函数，而实际上这种直观的近似方式是并不精确地。
他看似是线性的直线方程，但在一定数据量下也会出现非线性的状态，比如N的1.01次方，在数据量较小时，比如100，10，等，其结果偏差小于有效位，但足够大时，比如1000，10000，其偏差值会较大，而产生非线性情况。再比如1.001次方，1.0001次方，幂函数是非线性的。
其实这就是数据误差与计算机精度搞的鬼。
并不能统论任何运算都是非线性的，O(1)算法中最典型的例子是一种叫hash table，简单的说就是给每一个数据设定一个特殊的值，我在取数据时就能用这个特殊的值直接拿到不需要进一步计算，这样在宏观角度上将整个流程只经历了给特定值、取数据两个步骤，实际上消耗的时间是1个单位，并且，对于任意一个数据都有一个特定的值，那么对于任何一个值的取都只消耗一个单位，所要求取的数（N）与消耗时间并无关系，所以称为线性的，也就是O(1)的时间复杂度。★ -
奈嘉咲
