P2640 【神秘磁石】【判断质数】

2018-01-15 17:11:24


这道题,采用了新方法:Miller_Rabin 算法

因为这道题数据太小,所以也可以用其他方法

但是用这种算法的话会极大提升效率,时间复杂度为O(n),特别是遇到特别大的数的时候,更加明显,不过这种算法不稳定,但是这种不稳定的概率极小,小到几乎可以忽略不计

算法的理论基础:

1. Fermat定理:若n是奇素数,a是任意正整数(1≤ a≤ n−1),则 a^(n-1) ≡ 1 mod n。

2. 推演自Fermat定理(具体过程我没看懂,Orz), 如果n是一个奇素数,将n−1表示成2^s*r的形式,r是奇数,a与n是互素的任何随机整数,那么a^r ≡ 1 mod n或者对某个j (0 ≤ j≤ s−1, j∈Z) 等式a^(2jr) ≡ −1 mod n 成立。

那么我们按照上述的定理2,首先重复n次实验。对于每一次实验,随机取检验算子a,带入定理2进行检验,看看在算子a下,n能否满足

a^r ≡ 1 mod n或者对某个j (0 ≤ j≤ s−1, j∈Z) 等式a^(2jr) ≡ −1 mod n

如果任意一次实验不满足,则判定不是素数,如果都满足,可近似可以认为是素数(错误率极小)

    #include <iostream>
    #include <cstdio>
    #include <algorithm>
    #include <cmath>
    #include <cstring>
    #include <map>
    using namespace std;
    const int times = 20;
    int number = 0;
    map<long long, int>m;
    long long Random( long long n )            //生成[ 0 , n ]的随机数
    {
        return ((double)rand( ) / RAND_MAX*n + 0.5);
    }
    long long q_mul( long long a, long long b, long long mod ) //快速计算 (a*b) % mod
    {
        long long ans = 0;
        while(b)
        {
            if(b & 1)
            {
                b--;
                ans =(ans+ a)%mod;
            }
            b /= 2;
            a = (a + a) % mod;
        }
        return ans;
    }
    long long q_pow( long long a, long long b, long long mod ) //快速计算 (a^b) % mod
    {
        long long ans = 1;
        while(b)
        {
            if(b & 1)
            {
                ans = q_mul( ans, a, mod );
            }
            b /= 2;
            a = q_mul( a, a, mod );
        }
        return ans;
    }
    bool witness( long long a, long long n )//miller_rabin算法的精华
    {
        //用检验算子a来检验n是不是素数
        long long tem = n - 1;
        int j = 0;
        while(tem % 2 == 0)
        {
            tem /= 2;
            j++;
        }
        //将n-1拆分为a^r * s
        long long x = q_pow( a, tem, n ); //得到a^r mod n
        if(x == 1 || x == n - 1) return true;    //余数为1则为素数
        while(j--) //否则试验条件2看是否有满足的 j
        {
            x = q_mul( x, x, n );
            if(x == n - 1) return true;
        }
        return false;
    }
    bool miller_rabin( long long n )  //检验n是否是素数
    {
        if(n == 2)
            return true;
        if(n < 2 || n % 2 == 0)
            return false;                //如果是2则是素数,如果<2或者是>2的偶数则不是素数
        for(int i = 1; i <= times; i++)  //做times次随机检验
        {
            long long a = Random( n - 2 ) + 1; //得到随机检验算子 a
            if(!witness( a, n ))                        //用a检验n是否是素数
                return false;
        }
        return true;
    }
    int main( )
    {
        std::ios::sync_with_stdio(false);
        bool ok=0;
        long long n,k;
        cin>>n>>k;
        for(long long i=1;i<=n;++i)
        {
            if(miller_rabin(i)&&miller_rabin(i+k)&&i<=n&&i+k<=n)
            {
                cout<<i<<' '<<i+k<<endl;
                ok=1;
            }
        }
        if(ok==0)cout<<"empty"<<endl;
        return 0;
}