一、素数，也称质数，快速求素数的算法，是面试中经常遇到的问题

最简单的一种就是，把小于这个数的所有大于2的数挨着除一遍，如果有一个能被除尽，那么就不是素数
        public static boolean prim(int x){
                if(x<2){
                        return false;
                }
                for (int i = 2;i<x ;i++ )
                {
                        if(x%2==0){
                                return false;
                        }
                }
                return true;
        }
但是这个做法很蠢，因为大于x/2的数显然不能把x整除
所以，我们就有了第一种改进：
public static boolean prim1(int x){
                if(x<2){
                        return false;
                }
                for (int i = 2; i<x/2+1 ;i++ )
                {//循环到i的1/2+1为止
                        if(x/i==0){
                                return false;
                        }
                }
                return true;
        }

但是，我们知道取模运算 是非常非常慢的，这里我们有必要改进这个算法。
在这之前，我们必须提到一个数学上的定理：
二、费马小定理:（N^（P-1））%P = 1其中N为任意正整数，P为素数，且N与P互质
即：一个正整数N的P-1次幂对P的模为1

三、积模分解公式：(X*Y)%Z=((X%Z)*(Y%Z))%Z


证明如下:
      X>Z&&Y>Z时，必然有：
X=Z*I+A（1）
Y=Z*J+B（2）
将（1）和（2）代入(X*Y)modZ得：((Z*I+A)(Z*J+B))%Z
乘开，再把前三项的Z提一个出来，变形为：(Z*(Z*I*J+J*A+I*B)+A*B)%Z（3）


我们知道：
         如果有：X%Z=0，即X能被Z整除，则有：
(X+Y)%Z=Y%Z

把式三化简有：(A*B)%Z


又因为：A=X%Z，B=Y%Z，代入上面的式子，就成了原式了


当X>Z&&Y<Z时：
      X=Z*I+A
代入(X*Y)%Z得：
(Z*I*Y+A*Y)%Z
根据引理，转化得：(A*Y)%Z
因为A=X%Z，又因为Y=Y%Z，代入上式，即得到原式。
同理，X<Z&&Y>Z时，原式也成立。


X<Z&&Y<Z时，不用我证了吧


四、快速乘方运算
      快速计算乘方的算法

如计算2^13，则传统做法需要进行12次乘法。

/*计算n^p*/

int pow(int n,int p)
{
    for(int i=0;i<p;i++) {

                     n*=n;

     }
    return n;
}

2^13 = 2^6*2^6*2 = (2^2*2)*(2^2*2)*2

所以，上面的程序可以改成

int pow(int d n,int p)
{
   int main=n; //用main保存结果
   int odd=1; //odd用来计算“剩下的”乘积
   while (p>1)
   {//一直计算，直到指数小于或等于1
        if((p%2)!=0)
        {// 如果指数p是奇数，则说明计算后会剩一个多余的数，那么在这里把它乘到结果中

             odd*=main

        }
        main*=main;
        p/=2; //指数除以2
   }
   return main*odd;
}


但是我们知道，偶数的二进制表示法中的最低位一定为0!
所以我们可以改进

int pow(int d n,int p)
{
   int main=n; //用main保存结果
   int odd=1; //odd用来计算“剩下的”乘积
   while (p>1)
   {//一直计算，直到指数小于或等于1
        if((p&1)!=0)
        {// 如果指数p是奇数，则说明计算后会剩一个多余的数，那么在这里把它乘到结果中

             odd*=main

        }
        main*=main;
        p/=2; //指数除以2
   }
   return main*odd;
}
利用以上定理，我们可以得到我们需要的算法，这就是著名的蒙哥马利快速幂模算法：int Montgomery(int n,int p,int m)
{ //快速计算(n^e)%m的值
      int k=1;
       n%=m;
     while(p!=1)
     {
         if(0!=(p&1))k=(k*n)%m;
         n=(n*n)%m;
         p>>=1;
    }
    return(n*k)%m;
}
利用蒙哥马利判断素数的算法思路是这样的：
    对于N，从素数表中取出任意的素数对其进行费马测试，如果取了很多个素数，N仍未测试失败，那么则认为N是素数。当然，测试次数越多越准确，但一般来讲50次就足够了。另外，预先用“小学生”的算法构造一个包括500个素数的数组，先对Q进行整除测试，将会大大提高通过率，方法如下:


boolean prime2(int n)
{
    if ( n < 2 )
    { // 小于2的数即不是合数也不是素数
        return false;
    }
   int aPrimeList[] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37,41,
                        43, 47, 53, 59, 61,67, 71, 73, 79, 83, 89, 97};

    for (int i=0;i<aPrimeList.length;++i)
    { // 按照素数表中的数对当前素数进行判断
        if (1!=Montgomery(aPrimeList,n-1,n)
        {
            return false;
        }
    }
    return true;
}

求素数还有其他更加可靠的算法，目前最快的算法是拉宾米勒测试算法，我们这里就不在展开了

相信各位在面试中能说出蒙哥马利算法的思路原理就可以得到高分啦，

加油！

一、素数，也称质数，快速求素数的算法，是面试中经常遇到的问题

最简单的一种就是，把小于这个数的所有大于2的数挨着除一遍，如果有一个能被除尽，那么就不是素数
        public static boolean prim(int x){
                if(x<2){
                        return false;
                }
                for (int i = 2;i<x ;i++ )
                {
                        if(x%2==0){
                                return false;
                        }
                }
                return true;
        }
但是这个做法很蠢，因为大于x/2的数显然不能把x整除
所以，我们就有了第一种改进：
public static boolean prim1(int x){
                if(x<2){
                        return false;
                }
                for (int i = 2; i<x/2+1 ;i++ )
                {//循环到i的1/2+1为止
                        if(x/i==0){
                                return false;
                        }
                }
                return true;
        }

但是，我们知道取模运算 是非常非常慢的，这里我们有必要改进这个算法。
在这之前，我们必须提到一个数学上的定理：
二、费马小定理:（N^（P-1））%P = 1其中N为任意正整数，P为素数，且N与P互质
即：一个正整数N的P-1次幂对P的模为1

三、积模分解公式：(X*Y)%Z=((X%Z)*(Y%Z))%Z


证明如下:
      X>Z&&Y>Z时，必然有：
X=Z*I+A（1）
Y=Z*J+B（2）
将（1）和（2）代入(X*Y)modZ得：((Z*I+A)(Z*J+B))%Z
乘开，再把前三项的Z提一个出来，变形为：(Z*(Z*I*J+J*A+I*B)+A*B)%Z（3）


我们知道：
         如果有：X%Z=0，即X能被Z整除，则有：
(X+Y)%Z=Y%Z

把式三化简有：(A*B)%Z


又因为：A=X%Z，B=Y%Z，代入上面的式子，就成了原式了


当X>Z&&Y<Z时：
      X=Z*I+A
代入(X*Y)%Z得：
(Z*I*Y+A*Y)%Z
根据引理，转化得：(A*Y)%Z
因为A=X%Z，又因为Y=Y%Z，代入上式，即得到原式。
同理，X<Z&&Y>Z时，原式也成立。


X<Z&&Y<Z时，不用我证了吧


四、快速乘方运算
      快速计算乘方的算法

如计算2^13，则传统做法需要进行12次乘法。

/*计算n^p*/

int pow(int n,int p)
{
    for(int i=0;i<p;i++) {

                     n*=n;

     }
    return n;
}

2^13 = 2^6*2^6*2 = (2^2*2)*(2^2*2)*2

所以，上面的程序可以改成

int pow(int d n,int p)
{
   int main=n; //用main保存结果
   int odd=1; //odd用来计算“剩下的”乘积
   while (p>1)
   {//一直计算，直到指数小于或等于1
        if((p%2)!=0)
        {// 如果指数p是奇数，则说明计算后会剩一个多余的数，那么在这里把它乘到结果中

             odd*=main

        }
        main*=main;
        p/=2; //指数除以2
   }
   return main*odd;
}


但是我们知道，偶数的二进制表示法中的最低位一定为0!
所以我们可以改进

int pow(int d n,int p)
{
   int main=n; //用main保存结果
   int odd=1; //odd用来计算“剩下的”乘积
   while (p>1)
   {//一直计算，直到指数小于或等于1
        if((p&1)!=0)
        {// 如果指数p是奇数，则说明计算后会剩一个多余的数，那么在这里把它乘到结果中

             odd*=main

        }
        main*=main;
        p/=2; //指数除以2
   }
   return main*odd;
}
利用以上定理，我们可以得到我们需要的算法，这就是著名的蒙哥马利快速幂模算法：int Montgomery(int n,int p,int m)
{ //快速计算(n^e)%m的值
      int k=1;
       n%=m;
     while(p!=1)
     {
         if(0!=(p&1))k=(k*n)%m;
         n=(n*n)%m;
         p>>=1;
    }
    return(n*k)%m;
}
利用蒙哥马利判断素数的算法思路是这样的：
    对于N，从素数表中取出任意的素数对其进行费马测试，如果取了很多个素数，N仍未测试失败，那么则认为N是素数。当然，测试次数越多越准确，但一般来讲50次就足够了。另外，预先用“小学生”的算法构造一个包括500个素数的数组，先对Q进行整除测试，将会大大提高通过率，方法如下:


boolean prime2(int n)
{
    if ( n < 2 )
    { // 小于2的数即不是合数也不是素数
        return false;
    }
   int aPrimeList[] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37,41,
                        43, 47, 53, 59, 61,67, 71, 73, 79, 83, 89, 97};

    for (int i=0;i<aPrimeList.length;++i)
    { // 按照素数表中的数对当前素数进行判断
        if (1!=Montgomery(aPrimeList,n-1,n)
        {
            return false;
        }
    }
    return true;
}

求素数还有其他更加可靠的算法，目前最快的算法是拉宾米勒测试算法，我们这里就不在展开了

相信各位在面试中能说出蒙哥马利算法的思路原理就可以得到高分啦，

加油！