考察

\(M\) に対して \(k\) が良いための必要十分条件は、\(k\) と \(M\) が互いに素であることです。

また、\(M\) が完全であるための必要十分条件は \(M\) が素数であることです。

よって問題は「\(N\) 以上の最小の素数を求めよ」と読み替えられます。

ミラーラビン素数判定法

\(N\) が大きくテストケース数も多いため、試し割りによる素数判定を実行時間制限に間に合わせることは非常に困難です。そこでより高速な素数判定法として、ミラーラビン素数判定法[1]を用います。

ミラーラビン素数判定法は本来は確率的アルゴリズムですが、テスト対象の数が \(10^{12}\) 以下である場合は、 \((2,3,5,7,11)\) や \((2, 1215, 34862, 574237825)\) などを用いてテストすることで誤りなく判定を行えることが知られています[2]。

ミラーラビン素数判定法は、テストの回数を \(k\) として \(O(k\log N)\) 回の四則演算で判定を行うことができます。

\(N\leq 10^{12}\) の制約下では、合成数が連続する最大の長さは 539 である[3]ことから、素数判定を高々 \(540T\) 回行うことでこの問題を解くことができます。

実装例 (C++)

#include<bits/stdc++.h>
using namespace std;
using ll=long long;

ll modpowll(__int128 a, ll e, ll m){
  __int128 ret=1;
  while(e){
    if(e & 1) ret = ret * a % m;
    a = a * a % m;
    e /= 2;
  }
  return (ll)ret;
}

bool is_prime(ll n){
  vector<ll> a_list({2, 3, 5, 7, 11});
  if(n <= 2) return n == 2;
  if(n % 2 == 0) return false;
  ll d = (n-1) / ((n-1)&(1-n));
  for(ll a: a_list){
    ll t = d;
    a = modpowll(a, t, n);
    if(a == 0 || a == 1) continue;
    while(a != n-1){
      t *= 2;
      if(t == n-1) return false;
      a = (ll)((__int128)a * a % n);
      if(a == 1) return false;
    }
  }
  return true;
}

void solve(){
  ll n;
  cin >> n;
  int m = 0;
  while(!is_prime(n + m)){
    m++;
  }
  cout << m << endl;
}

int main(){
  int t;
  cin >> t;
  while(t--){
    solve();
  }
}

実装例 (Python)

def is_prime(n):
  a_list = [2, 3, 5, 7, 11]
  if n <= 2: return n == 2
  if n % 2 == 0: return False
  d = (n-1) // ((n-1)&(1-n))
  for a in a_list:
    t = d
    a = pow(a, t, n)
    if a == 0 or a == 1: continue
    while a != n-1:
      t *= 2
      if t == n-1: return False
      a = a * a % n
      if a == 1: return False
  return True

def solve():
  n = int(input())
  m = 0
  while not is_prime(n + m):
    m += 1
  print(m)

T = int(input())
for _ in range(T):
  solve()