test/verify/math/yosupo-primality-test.test.cpp

View this file on GitHub
Last update: 2026-05-11 00:18:16+09:00
Problem: https://judge.yosupo.jp/problem/primality_test

Depends on

Code

#define PROBLEM "https://judge.yosupo.jp/problem/primality_test"

#include "template/template.hpp"
#include "math/primality_test.hpp"

int main() {
  ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

  int Q; cin >> Q;
  while(Q--) {
    unsigned long long n; cin >> n;
    cout << (is_prime(n) ? "Yes" : "No") << '\n';
  }
}

#line 1 "test/verify/math/yosupo-primality-test.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/primality_test"

#line 1 "template/template.hpp"
#include <iostream>
#include <cassert>
using namespace std;
using ll = long long;
template<class T> inline bool chmax(T& a, const T& b) {if (a<b) {a=b; return true;} return false;}
template<class T> inline bool chmin(T& a, const T& b) {if (b<a) {a=b; return true;} return false;}
const int INTINF = 1000001000;
const int INTMAX = 2147483647;
const ll LLMAX = 9223372036854775807;
const ll LLINF = 1000000000000000000;
#line 1 "math/primality_test.hpp"



#include <cstdint>

namespace primality_test_internal {

using u64 = unsigned long long;
using u128 = unsigned __int128;

inline u64 mod_pow_u64(u64 a, u64 e, u64 mod) {
  u64 ret = 1;
  while(e > 0) {
    if(e & 1) ret = (u128)ret * a % mod;
    a = (u128)a * a % mod;
    e >>= 1;
  }
  return ret;
}

inline bool miller_rabin(u64 n, u64 a, u64 d, int s) {
  if(a % n == 0) return true;
  u64 x = mod_pow_u64(a, d, n);
  if(x == 1 || x == n - 1) return true;
  for(int i=1; i<s; i++) {
    x = (u128)x * x % n;
    if(x == n - 1) return true;
  }
  return false;
}

} // namespace primality_test_internal

inline bool is_prime(unsigned long long n) {
  using namespace primality_test_internal;
  if(n < 2) return false;
  for(u64 p: {2ULL, 3ULL, 5ULL, 7ULL, 11ULL, 13ULL, 17ULL, 19ULL, 23ULL, 29ULL, 31ULL, 37ULL}) {
    if(n == p) return true;
    if(n % p == 0) return false;
  }

  u64 d = n - 1;
  int s = 0;
  while((d & 1) == 0) {
    d >>= 1;
    s++;
  }

  for(u64 a: {2ULL, 3ULL, 5ULL, 7ULL, 11ULL, 13ULL, 17ULL, 19ULL, 23ULL, 29ULL, 31ULL, 37ULL}) {
    if(!miller_rabin(n, a, d, s)) return false;
  }
  return true;
}


#line 5 "test/verify/math/yosupo-primality-test.test.cpp"

int main() {
  ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

  int Q; cin >> Q;
  while(Q--) {
    unsigned long long n; cin >> n;
    cout << (is_prime(n) ? "Yes" : "No") << '\n';
  }
}