题解：
会了Miller-Rabin这题就很简单了
首先这种题很容易想到质因数分解
但是暴力根号算法是不行的
所以要用到
Miller-Rabin素数
https://blog.csdn.net/ltyqljhwcm/article/details/53045840
对于要判断的数n
1.先判断是不是2，是的话就返回true。
2.判断是不是小于2的，或合数，是的话就返回false。
3.令n-1=u*2^t，求出u，t，其中u是奇数。
4.随机取一个a,且1<a<n
/*根据费马小定理，如果a^(n-1)≡1(mod p)那么n就极有可能是素数，如果等式不成立，那肯定不是素数了
因为n-1=u*2^t，所以a^(n-1)=a^(u*2^t)=(a^u)^(2^t)。*/
5.所以我们令x=(a^u)%n
6.然后是t次循环，每次循环都让y=(x*x)%n，x=y,这样t次循环之后x=a^(u*2^t)=a^(n-1)了
7.因为循环的时候y=(x*x)%n，且x肯定是小于n的，正好可以用二次探测定理，
如果(x^2)%n==1，也就是y等于1的时候，假如n是素数，那么x==1||x==n-1，如果x!=1&&x!=n-1，那么n肯定不是素数了，返回false。
8.运行到这里的时候x=a^(n-1)，根据费马小定理，x!=1的话，肯定不是素数了，返回false
9.因为Miller-Rabin得到的结果的正确率为 75%，所以要多次循环步骤4~8来提高正确率
10.循环多次之后还没返回，那么n肯定是素数了，返回true
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int kk=;
ll n;
ll C(ll x,ll y)
{
if (y==) return(x);
if (y%==) return(((C(x,y/)*)%n+x)%n);
else return((C(x,y/)*)%n);
}
ll M(ll x,ll y)
{
if (y==) return(x);
ll tmp=M(x,y/);
if (y%==) return(C(C(tmp,tmp),x));
else return(C(tmp,tmp));
}
bool pd()
{
if (n==) return ;
if (n<) return ;
ll m=n-;
int k=;
while (!(m&))
{
k++; m>>=;
}
for (int i=;i<=kk;i++)
{
ll x1=rand()%(n-)+;
ll x2=M(x1,m);
ll y=;
for (int j=;j<=k;j++)
{
y=C(x2,x2);
if (y==&&x2!=&&x2!=n-) return ;
x2=y;
}
if (y!=) return ;
}
return ;
}
int main()
{
// freopen("1.in","r",stdin);
// freopen("1.out","w",stdout);
while (cin>>n)
{ if (pd()) cout<<"T"; else cout<<"F";
cout<<endl;
}
return ;
}
Pollard-rho算法：