数据处理：
（1）gcd (Greatest Common Divisor):
gcd详解：（2）素数 （质数）（prime number）：
（2.1）判断素数 ：
（2.1.1）试除法 ：
（2.1.2）筛选法 ：
（2.2）前N个素数 ：
（2.3）小于等于N的素数 ：
------------------------------------------------------------
（1）辗转相除法gcd : Greatest Common Divisor
（1.1）简介 ：
gcd，即辗转相除法，又称欧几里得算法，是求最大公约数的算法，即求两
个正整数之最大公因子的算法。
gcd 算法：给定俩个正整数m，n（m>=n），求它们的最大公约数。（注意，
一般要求m>=n，若m<n，则要先交换m<->n。下文，会具体解释）。
用数学定理表示即为：“定理：gcd(a,b) = gcd(b,a mod b) (a>b 且a mod
b 不为0)”。以下，是此算法的具体流程：
（1.2）步骤：
1、[求余数]，令r=m%n，r 为n 除m 所得余数（0<=r<n）；
2、[余数为0?]，若r=0，算法结束，此刻，n 即为所求答案，否则，继续，
转到3；
3、[重置]，置m<-n，n<-r，返回步骤1.
（1.3）代码实现 ：
int gcd(int a,int b){
int temp;
if(a<b){/*交换两个数，使大数放在a上*/
temp=a;
a=b;
b=temp;
}while(b!=0){
/*利用辗除法，直到余数为0为止,则最大公约数为除数
此中余数为temp,b=temp;
*/
temp=a%b;
a=b;
b=temp;
}
return a;
}递归实现 ：
int gcd(int a,int b){
int temp;
int gcd;
if(a<b){/*交换两个数，使大数放在a上*/
temp=a;
a=b;
b=temp;
}
while(b%a!=0){
gcd=gcd(b,b%a);
}
return gcd;
}
（1.3）a模p的乘法逆元：
a存在模p的乘法逆元的充要条件是gcd(a,p) = 1
a*b=kp+1;
则称b为a模p的乘法逆元。
（1.4）如果gcd(a,b)=d，则存在m,n，使得d = ma + nb，
称呼这种关系为a、b组合整数d，m，n称为组合系数。
(类似于ax+by=c;然后c为组合数，a,b为组合系数)
当d=1时，有 ma + nb = 1 ，此时可以看出m是a模b的乘法逆元，
n是b模a的乘法逆元。
--------------------------------------------
（2）素数（质数）(prime number) ：
（2.0）素数定理 ：
描述某个范围内的素数个数 ：
对正实数x，定义π(x)为不大于x的素数个数。
其中lnx为x的自然对数。上式的意思是当x趋近∞，
π(x) ≈ x/ln x 。
（2.1）判断素数 ：
判断一个数是否为素数，一般的书上都是写的 %（模）它的前一般数。 若出现整除break;
上面的那种方法效率很低，根据自然数分解定理，
每一个合数都可以分解成 一些素数的乘积，
也就是说，如果一个数不能整除任一个比它小的素数，则它必然是素数！
还有1不是素数，也不是和数。
（2.1.1）试除法 (适用于判断一个数是否为素数)：
（1）判断质数境界一：
从2~n-1;依次除以n；
（2）判断质数境界二：
想：如果n有从自身以外的因数，肯定小于等于n/2;
所以从2~n/2;
（3）判断质数境界三：
想：除2以外，所有可能的质因数都是奇数，
所以：先尝试2，然后从3开始一直到n/2的奇数。
（4）判断质数境界四：
先尝试2，然后从3到√x 的奇数；
代码如下：
bool isPrime(int value){
if(value%2==0)
return false; int sqrtOfValue=sqrt(value);
for(int i=3;i<=sqrtOfValue;i+=2){ if(value%i==0)
return false;
} if(i>sqrtOfValue)
return true; }（5）判断质数境界五：
从2开始到√x 的质数；
1.先构建从2到√x 的素数数组；
2.然后不断查表。
--------------------------
（2.1.2）筛选法 （使用与输出小于等于N的素数）：
(1)筛选法简介 ：
因为任何一个合数都可以表示为若干个素数的乘积。
所以去掉素数的整数n(n>1)倍的数，就剩下的就是素数了。
所以：先去掉2的整数倍（2除外）
再去掉3的整数倍。
.....
2是公认最小的质数，所以，先把所有2的倍数去掉；然后剩下的那些大于2的数里面，最小的是3，所以3也是质数；然后把所有3的倍数都去掉，剩下的那些大于3的数里面，最小的是5，所以5也是质数......上述过程不断重复，就可以把某个范围内的合数全都除去（就像被筛子筛掉一样），剩下的就是质数了。
(2) 图解 ：
(3) 构造存储容器 ：
知道了分布范围，接下来就得构造一个容器，来存储该范围内的所有自然数；然后在筛的过程中，把合数筛掉。
（1）境界一：整型存储
解析：
直接构造一个整型的容器。在筛的过程中把发现的合数删除掉，最后容器中就只剩下质数了。
缺点：整型的容器，浪费内存空间。
（2）境界二：bool型存储 ：
解析：
构造一个定长的布尔型容器（通常用数组）。
。比方说，质数的分布范围是1000000，那么就构造一个包含1000000个布尔值的数组。然后把所有下标为奇数以及下标为2的设置为true，下标为偶数且>2的设置为false。在筛选的过程中，发现某个下标时素数，则把下标是素数下标 的整数倍的元素设置为false。全部筛完之后，遍历数组，找到那些值为 true 的元素，把他们的下标打印出来即可。
改进：bool型数组里面只存奇数不存偶数。如定义prime[N],则0表示3，1表示5，2表示7，3表示9...。如果prime[0]为true,则表示3时素数。prime[3]为false意味着9是合数。
（3）境界三 ：按位存储 （byte 数组）：
解析：一个字节八位，然后求一定范围range的质数，byte[range]
初始化为全为1,然后将以合数为下标的元素值设为0.
这样整个数组就是一个01串。
最后得到，元素值为1的下标即可。
（4）境界四：
----------
（2.2）求取前n个素数 ：
（2.2.1）试除法 ：
（1）思路：
前面3个素数2，3，5；后面检验的就可以在原来素数的基础上+2，比如要找第四个素数
就在5的基础上+2，然后再用5+2整除前面的素数2，3，5如果都不能整除那就是素数
其他的以此类推。
（2）代码实现 ：
/*
输入：取前n个素数；
输出：前n个素数的 数组，以及返回第n个素数的 值。
*/
int get_primesArray(int *primeArray, int length)
{
primeArray[0] = 2;
primeArray[1] = 3;
int count = 1;
for(int i=3; count!=length; i+=2)
{
int sqrt_i = sqrt(i); for(int j=1; sqrt_i>=primeArray[j] && i%primeArray[j]!=0; ++j);
/*
试除法判断一个数i是否为素数，
就是用从2到sqrt(i) 的素数去除 i，看是否可以整除。
此中素数存储在数组中，另外j从1开始，因为i为奇数。
所以不需要从2=primeArray[0]开始除了 。
*/ if(sqrt_i<primeArray[j])
{
primeArray[count++] = i;
}
}
return primeArray[count-1];
}
（2.2.3）筛选法求前n个素数 ：
(1)分析 ：
根据素数定理，求前n个素数，需要先确定素数分布的范围。
因为这个质数分布公式有一定的误差（通常小于15%）。
为了保险起见，把反推出的素数分布范围再稍微扩大15%，应该就足够了。
（2）步骤：
1. 由素数定理确定范围 ：
2. 转化为求一定范围内的素数 ：
（2.2.4）代码实现 ：
------------
（2.3）求取小于N的所有素数 ：
（2.3.1）思路一：筛选法，可以将bool数组，改为byte数组，节约空间。
(2.3.1.1)步骤：
（1）初始化筛选数组，偶数下标设为0（false）,奇数为1（true）。
（2）将每个素数下标的奇数倍(n为奇数，n>=3)的元素设置为0(false).
(2.3.1.2)代码实现 ：
void init(bool * primeArray,int length){
for(int i=2;i<length;i+=2){
primeArray[i]=false;
primeArray[i-1]=true;
}
/*
如果数组最后几个元素为：
i-1,i ,i+1 （即i+1=N-1）
则i+1没有初始化，循环结束时i=N=偶数; 如果最后几个为i-1,i（即i=N-1）
则正常,循环结束时i=N+1=偶数; if(i==N)
prime[N-1]=true;
因为i始终为偶数。
*/ if(i==length){
primeArray[length-1]=true;
} primeArray[2]=true;
} void primeLessThanN(int n,bool * primeArray,int length)
{
/*其实length=n+1;不需要额外传递*/
init(primeArray,length); for(int i=3;i<=sqrt(n);i+=2){
/*
因为下标是2的整数倍的都已经设为false，所以从3开始，
然后只有奇数才有可能为素数，所以i+=2;
然后为什么是i<=sqrt(N) ????
因为任何一个合数x，都可以表示为素数的乘积，所以素数是合数的因数。
所以该素数<=sqrt(x);
*/
if(primeArray[i])
{
/*该下标是素数
则把下标是素数下标整数倍的元素设为false。
此中j=3*i;是因为2*i是2的倍数，值必然为false。
然后不用j+=i;因为i的偶数倍的值必然为false。
*/ for(j=i*3;j<N;j+=2*i){
primeArray[j]=false;
} }
}
}
---------------------------------------------
（2.4）前n个素数 && 小于等于n的素数 代码测试
标签：false,gcd,int,质数,素数,&&,legend,primeArray From： https://blog.51cto.com/u_15911260/5934916