素数是什么
素数是什么？
素数就是只有1和本身两个因数的自然数。1不是素数，2是最小的素数。扩展一下思考，可以得出结论，所有的非素数，可以写成几个素数的乘积，即如下等式成立：
任何一个非素数 = 素数a * 素数b * 素数c 。。。。。。。 |
所以说，素数英文名为prime numbe，基本数。
素数行踪不定，分布没有任何规律，没有任何一个公式可以表达出所有的素数，然而素数又如此特别，吸引了从古到今一批又一批的数学家投身于素数的研究。而现在得益于计算机的发展，计算能力达到了过去无法想象的级别，我们在研究素数上走的更远了，但是依然是站在巨人的肩膀上。我以我的浅薄的理解梳理一下前人的研究成果：
素数的个数：
欧几里得：通过反证法证明素数有无穷多个。证明过程如下：假设素数的个数为有限个，回顾前文可知，任何非素数可以表示为N个素数的乘积，那么一定存在一个非素数等于所有素数乘积为X，X+1显然不能被这些素数整除。这一个结果与假设相悖，说明素数的个数为无穷多个。
素数的分布：
天才少年高斯在15岁的时候，就观察到对于一个整数X，小于X的这些整数中，素数的个数大致等于x除以loge x，loge 又叫做自然对数，即以e为低的对数。e约等于2.71828。也就是说如下等式大致成立，在x较小时，只是近似成立。
f(x) = x/lnx |
才疏学浅，e和自然对数又能扩展到很多，我就不展开了。
孪生素数：
相差为2的素数对，比如3和5，5和7，11和13。
孪生素数猜想：存在无穷多个素数p，使得p+2也是素数
1849年，法国数学家伯林那克提出更加一般的猜想：对于所有的自然数k，存在无穷多个素数对（p,p+2k）。k=1时就是孪生素数猜想。
梅森素数：
梅森数是指形如2^p－1的正整数，其中p为素数，如果这个梅森数是一个素数，那么就叫做梅森素数。千百年来，包括欧几里得、费马、欧拉都在寻找梅森素数。在进入计算机时代之前的两千年左右，人们历经艰辛，一共找到了12个梅森素数。进入互联网时代后，世界上第一个基于互联网的分布式计算项目——因特网梅森素数大搜索（https://www.mersenne.org/），诞生了。2017年12月26日，我们终于找到了第五十个梅森素数——2^77232917-1。
费马小定理：
假如p是质数，且gcd(a,p)=1，那么 a(p-1)≡1（mod p）。即：假如a是整数，p是质数，且a,p互质(即两者只有一个公约数1)，那么a的(p-1)次方除以p的余数恒等于1。
哥德巴赫猜想：
偶数版本（欧拉表述）：任何一个大于2的偶数都可以由两个素数相加得到。
奇数版本：任何一个大于7的奇数都可以由三个素数相加得到。
显然，偶数版本可以推出奇数版本。奇数版本的证明在1937年就由苏联数学家Vinogradov近似地证明了：对于足够大的奇数都可以表示成三个素数之和。但是偶数版本的证明现在还遥遥无期，目前最接近的研究时中国数学家陈景润的研究。他证明了1+2问题，也就是说：对于足够大的偶数都可以由一个素数和一个自然数相加得到，这个前者可以表示为两个素数的乘积。
足够大的偶数=素数a+ 素数b*素数c |
另外说一句，哥德巴赫猜想的证明对人类社会没有重大推动作用，更加类似于运动员挑战人体的极限。当然在这个证明的过程中，可能会由新的理论提出，新的方法被发现，这些也许是有用的。又因为哥德巴赫猜想的表述太简单，一个小学毕业生都可以理解，所以这里一直是民科的重灾区。
如何判断一个数是素数？
试除法
对于给定的n，直接判断2~n-1中是否存在n的约数即可。
显然，仔细一思考，就能发现，这样效率太低。对于每个数n，其实并不需要从2判断到n-1，我们知道，一个数若可以进行因数分解，那么分解时得到的两个数一定是一个小于等于sqrt(n)，一个大于等于sqrt(n)，据此，上述代码中并不需要遍历到n-1，遍历到sqrt(n)即可，因为若sqrt(n)左侧找不到约数，那么右侧也一定找不到约数。改进代码如下：
再思考一下，我们需要对2~sqrt(n)中的每一个数取余么？其实也不需要。回顾前文，任何一个非素数都可以分解成唯一的几个素数的乘积的形式。那么假设我已知了2~sqrt(n)范围内的所有素数，对于n，只需要判断，这些素数中，是否有n的约数即可。改进代码如下
其中primeArr为保存了所有素数的一个数组。
前段时间正好面试要求我现场写一个判断素数的程序，三十分钟后我交上了答案几乎就是上图的代码（此处可否不要脸的求一波掌声？）
当要判断的素数大小超过1亿时，试除法开始力不从心了。
Miller-Rabbin素数测试法：
首先引入一个新概念：伪素数。 如果n是一个正整数，如果存在和n互素的正整数a满足a^(n-1)≡1(mod n)，我们说n是基于a的伪素数。
如果一个数是伪素数，它几乎就是素数。另一方面，如果一个数不是伪素数，它一定不是一个素数。那么在一定的条件下，如果我们选取了若干个基都发现n是伪素数， 那么n是素数的概率趋近于1。
现在我们只需要多次寻找不超过n-1基并检验是否有a^(n-1)≡1(mod n)， 如果一直有， 那么这个数就是一个素数， 否则可以立即判定这个数是个合数。这个寻找次数可以设为s，可以证明，经过s次检测以后，出错的概率为(1/4)^s。
素数到底能干什么？
密码学
首先从大家能够比较直观的简单加密说起把。凯撒加密：将字母循环后移n位。后移就是加密的算法，n则为密钥。假设我要传输的明文为：“i love you”，我的密钥为4，加密后得到的密文为：“m pszi csy”（表白预警）。一般来说加密算法是公开的，密钥则是敏感信息。我们对明文进行加密，要知道密钥，对密文进行解密，也需要知道密钥。通过同一个密钥进行加密解密的算法统统叫做对称加密算法。以目前业界通用的DES对称加密算法，整个加密过程非常复杂，看上去是很安全的，但是对称加密算法有一个巨大的缺陷：安全性依赖于密钥，如果密钥泄露就等于任何人可以解密密文，密钥的保密性对通信的安全性至关重要。
1976年， 美国学者Dime和henman提出了非对称加密算法。该算法需要两个密钥，公钥和私钥。加密通过公钥进行，但是必须通过私钥才能解密。这个算法的重大意义在于，互联网往往都是1：N的关系，1个server对应成千上万个client，如果使用传统的对称加密算法，要么所有的client使用同一个密钥（非常不安全），要么server为每一个client维护一个密钥（成本高）。但是有了非对称加密算法，server可以放心的广播出去公钥，因为解密需要私钥。
这里稍微扩展一下，比较常见的非对称加密算法就是rsa算法。大家打开任何一个https的网站，左上角都可以查看https证书信息，里面就包括了加密算法（一般都是RSA）和一个很长的公钥字符串。
RSA算法原理：
我们以一个简单的例子来示范一下。
1.选择p=5，q=11，为了方便理解和计算。大数的因数分解非常难。
2.计算出n=55，欧拉公式φ(n)=(5-1)*(11-1)=4*10=40.
3.选择一个随机整数e，大于1小于40，并且e和40的最大公约数为1。那我就选e=7吧
4.根据d*e=1modφ(n)，也就是说 7d = 1 mod 40,得出d=23.
5.最后我们得知{7,55}为公钥，{23，55}为私钥。
6.加密：根据{7,55}公钥对明文 =8进行加密，加密后 8^7 = 2097152 然后再对n=55取余，得到的密文为2
7.解密，2^23 = 8388608，对于55取余的结果为8，即，明文=8。
相关阅读
首先需要理解什么是素数（也就是我们常说的质数）：即一个只能被自身或1整除的数整除即为质数。（搞清楚： a 能被 b整除 ， a是被除数，b是除数
问题 A(2266): 【基础算法】素数环 时间限制: 5 Sec 内存限制: 128 MB 提交: 224 解决: 102 [提交][状态][我的提交] 题目描述
素数环NOJ1104回溯法应用，显然解空间是一个排列集，n最大为16，最大解空间为16！= 2*10^13（阶乘）。用next_permutation生成每排列，然后判断
安全素数 安全素数是满足2p＋1形式的一类数，在这里p也是素数。（相反地，素数p叫做索菲热尔曼素数。）若p1=2*p2+1，则p1称为安全素数，p2称为
int t=0; //素数的个数 Random ran = new Random(); double [] a = new double [10]; Console.Writ