【SP288 PON - Prime or Not】题解

斜揽残箫 · 2021-07-14 08:34:43 · 题解

Solution

对于素数判定，有一个很简单的暴力做法 ：

bool prime(int num)
{
    if(num == 1) return false;
    for(int i = 2;i * i <= n;i ++) {
        if(num % i == 0) return false;
    }
    return true;
}

但是这个的时间复杂度明显是 \sqrt n 的，而题面中的 2 \leq n \leq 2 ^ {63} - 1 已经告诉了你的代码应该会跑一天。

所以我们需要更快的判定方式，也就是 Miller_Rabin 算法。

Miller_Rabin 算法

引理 ： Ex费马小定理

如果 n 为素数，则 \forall a < n，设 n - 1 = d \times 2 ^ r，d 为奇数，则以下两个命题至少有一个成立 ：

• a ^ d \equiv 1 \pmod n
• \exists 0 \leq i < r,\text{s.t.}a ^ {d \times 2 ^ i} \equiv -1 \pmod n

但是他的逆命题不一定成立，所以 Miller_Rabin 算法是一个有概率出错的算法。

证明可以上 oi-wiki。

所以我们可以取一些数 (1 \leq a_1,a_2,a_3,\cdots,a_m < n) 代入到其中进行测试，如果都成立，说明要判断的数可能是质数。

进行这个操作可以用 rand() 随机生成几个大于等于 1，小于 n 的数来测试，这种情况你如果你脸实在黑，挂掉了，那就再交一遍吧。

如果我们要减小出错的概率，就可以用几个 100 以内的质数，一般要测 8 \sim 10 次就可以了。

可以取一个 [2,3,5,7,11,23,37,41,79] 一般都不会被卡。

温馨提示，要用龟速乘。

Code

#include <cstdio>
#include <cmath>
#include <iostream>
#include <cstring>
#include <algorithm>
#define int long long
using namespace std;
int prime[12] = {0,2,3,7,13,97,37,29};
inline int read()
{
    int s = 0, f = 0;char ch = getchar();
    while (!isdigit(ch)) f |= ch == '-', ch = getchar();
    while (isdigit(ch)) s = s * 10 + (ch ^ 48), ch = getchar();
    return f ? -s : s;
}
int mul(int a,int b,int mod)
{
  int res = 0;
  while(b) {
    if(b & 1) res = (res + a) % mod;
    a = (a + a) % mod;
    b >>= 1;
  }
  return res % mod;
}
int KSM(int a,int b,int mod)
{
  int ans = 1;
  while(b) {
    if(b & 1) ans = mul(ans,a,mod);
    a = mul(a,a,mod);
    b >>= 1;
  }
  return ans;
}
bool Miller_Rabin(int n,int a)
{
  int d = n - 1,r = 0;
  while(n % 2 == 0) r ++,n /= 2;//根据定理，把要求的数的 2 的因子取出来 
  int x = KSM(a,d,n);
  if(x == 1) return true;
  for(int i = 0;i < r;i ++) {
    if(x == n - 1) return true;
    x = mul(x,x,n);
  }
  return false;
}
bool check(int n)
{
  for(int i = 1;i <= 7;i ++) {
    if(n == prime[i]) return true;
    if(n % prime[i] == 0) return false;
    if(Miller_Rabin(n,prime[i]) == false) return false;
  }
  return true;
}
signed main()
{
  int T = read();
  while(T --) {
    int n = read();
    if(check(n)) cout << "YES" << endl;
    else cout << "NO" << endl;
  }
  return 0;
}