素数的定义
定义：在一个大于0的自然数中，除了1和此整数自身外，不能被其他自然数整除的数。
问题 1、判断一个数是否为素数
问题 2、求解[1,n]之间的素数
问题 3、求解 N 个素数。
问题 4、求解不小于n的最小素数
————————
问题 1、判断一个数是否为素数
思路<1> 试除法
思路<2> 试除法 + 抛去偶数
思路<3> 试除法 + 抛去偶数 + 缩小试除范围
思路<4>对素数试除法 + 减少扫描区间
—————–
思路(1) 试除法
基本思路：判断n是否为素数时，检查区间[2,n – 1]之间的数是否能整除n。
代码：
bool IsPrime(int nNum){for (int i = 2;i < nNum;i++){if (nNum % i == 0){return false;}}return true;}
思路(2) 试除法 + 抛去偶数
具体思路：素数肯定是奇数，因为偶数肯定能被2整除，所以在检查区间[2,n – 1]之间的数时，只判断奇数是否能整除n即可。
代码：
///试除法 + 刨除偶数bool IsPrime(int nNum){if (nNum == 2)//2是素数，直接返回{return true;}if ((nNum & 1) == 0)//刨除偶数{return false;}for (int i = 3;i < nNum;i += 2){if (nNum % i == 0){return false;}}return true;}注意：
(1)如果直接写for循环，那么上述代码就会错误的判断偶数为素数，因此需要把偶数单独处理，直接判断其是否为偶数。
(2)在单独处理偶数时，这里使用位操作进行做的，效率比取余操作高。
思路(3)试除法 + 抛去偶数 + 缩小试除范围
具体思路：思路 1和思路 2的试除范围都在[2,n – 1]，其实范围可以限制在[2,sqrt[n]]，因为如果一个数不是素数，那么它肯定有至少有俩因子，而且因子也是成对出现的，而且一个因子是大于sqrt[n]的,一个因子是小于sqrt[n]的。
举例，100，可以分解为2 * 50、4 * 25、5 * 20、10 * 10
所以，对于每一对因子，我们只需要检查其小于sqrt[n]的因子即可，如果能整除，肯定也能被另一个因子整除。这样就能直接判断其是否能分解成成对的俩因子。
代码：
///试除法 + 刨除偶数 + 减少扫描区间bool IsPrime(int nNum){if (nNum == 2){return true;}if ((nNum & 1) == 0)//刨除偶数{return false;}for (int i = 3;i * i <= nNum;i += 2){if (nNum % i == 0){return false;}}return true;}思路(4)对素数试除法 + 减少扫描区间
分析：
（1）合数（不是素数就是合数）是由若干个质数相乘而得来的,比如，合数6是有素数2和3相乘得到。15是由素数3和5相乘得到。
（2）前几个思路使用试除法时，，也对合数进行了取余，所以造成浪费。比如判断103是否为素数时，如果采用试除法 + 抛去偶数 + 缩小试除范围的方法，则需要取余的整数为2,3,5,7,9,10。我们可以观察3和9，如果一个数N能被9整除，那么它肯定能被3整除。反过来说，如果N不能被3整除，则肯定不能被9整除。因此我们只需要检查3即可。对于10也是，如果N不能被2和5整除，它肯定也不能被10整除。
因此，我们要判断数N是否是素数时，只需要对[1,sqrt(N)]之间的素数进行试除即可。
注意，这里的前提是我们已知[1,sqrt(N)]之间的素数。
代码：假设我们已经知道素数集合nArrPrimeTable中，素数个数为nCount个。
//对素数试除法 + 减少扫描区间bool IsPrime(int nNum){if (nNum == 2){return true;}for (int i = 0;i < nCount && nArrPrimeTable[i] * nArrPrimeTable[i] <= nNum;i++){if (nNum % nArrPrimeTable[i] == 0){return false;}}return true;}
此时的问题，就是怎么构造素数表? 这就是我们要解决的问题2。
思路(5) 预先存储所有素数 + 二分查找
思路(6) 预先存储所有素数 + O(1)查找
—————–第一个问题结束——————
现在的问题变成怎么求解[1,N]之间的素数。
问题 2、求解[1,n]之间的素数
要解决这个问题，必须要解决一个问题：用多大的数组存储这些素数？
这里可以使用素数定理，确定1-N之间的素数。
这里采用博主编程随想的说法，确定小于N的素数个数 = x/ln(x)，公式中的 ln 表示自然对数。
假设要估计1,000,000以内有多少质数，用该公式算出是72,382个，而实际有78,498个，误差约8个百分点。
该公式的特点是：估算的范围越大，偏差率越小。
根据素数定理，可以根据最大值n，求解出[1,n]之间素数的个数，由于公式有误差，我们可以在x/ln(x)的基础上，扩大50%。
注意原文章扩大15%，貌似有误差。当N = 490时，求出[1,490]之间的素数为93个，但是1.15 *x/ln(x) = 90.9。
故，扩大15%还是不够的，我们这里为了简单，就扩大了50%。
下面给出具体的方法：
(1)试除法
(2)埃拉托斯特尼筛法
——————
具体来说，为了加速求解素数，这里采用试除法中最快的方法，即对素数试除法 + 减少扫描区间
无论身处何处，只要有一颗放松而美好的心态，生活便是美好！
