这道题,采用了新方法: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
如果任意一次实验不满足,则判定不是素数,如果都满足,可近似可以认为是素数(错误率极小)
```cpp
#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;
}
```