// SPDX-License-Identifier: MIT // (c) 2023 TwoSquirrels // my AtCoder environment: https://github.com/TwoSquirrels/atcoder-env #ifndef INCLUDED_MAIN # define INCLUDED_MAIN # include __FILE__ inline void cp_main() { int n=scan; for(int i=0;i) # include #else // C++17 (clang) # include # include # include # include # include # include # include # include # include # include # include # include # include # include # include # include # include # include # include # include # include # include # include # include # include # include # include # include # include # include # include #endif // boost libraries #if __has_include() # define INCLUDED_BOOST_CPP_INT # include #endif #if __has_include() # define INCLUDED_BOOST_PRIME # include #endif #if __has_include() # define INCLUDED_BOOST_MILLER_RABIN # include #endif // atcoder libraries #if __has_include() # define INCLUDED_ACL # include #endif /// sfinae #if __cplusplus >= 202002L template concept IsInputable = requires (T a) { std::cin >> a; }; template concept IsPair = requires (T a) { a.first; a.second; }; template concept IsEachable = requires (T a) { std::begin(a); std::end(a); }; #endif // C++20 /// utils template constexpr int sin90(T theta90) { if (theta90 % 2 == 0) return 0; return theta90 % 4 < 2 ? 1 : -1; } template constexpr int cos90(T theta90) { return sin90(theta90 + 1); } template constexpr int sin45(T theta45) { if (theta45 % 4 == 0) return 0; return theta45 % 8 < 4 ? 1 : -1; } template constexpr int cos45(T theta45) { return sin90(theta45 + 2); } template inline bool chmin(T &&a, const U b) { const bool compare = a > b; if (compare) a = b; return compare; } template inline bool chmax(T &&a, const U b) { const bool compare = a < b; if (compare) a = b; return compare; } long long int powi(int base, int exponent = 2) { long long int ans = 1; for (int i = exponent; i != 0; i += (i >= 0 ? -1 : 1)) { if (i >= 0) ans *= base; else ans /= base; if (ans == 0) break; } return ans; } template bool is_prime(T n) { if (n <= 1) return false; if (n == 2 || n == 3) return true; if (n % 2 == 0 || n % 3 == 0) return false; // miller rabin #ifdef INCLUDED_ACL if (n <= 1LL << 32 && n <= std::numeric_limits::max()) { //return atcoder::internal::is_prime_constexpr(n); } #endif // INCLUDED_ACL #ifdef INCLUDED_BOOST_MILLER_RABIN //return boost::multiprecision::miller_rabin_test(n, 25); #endif // INCLUDED_BOOST_MILLER_RABIN // binary search #ifdef INCLUDED_BOOST_PRIME if (n <= boost::math::prime(boost::math::max_prime)) { /*int left = 0, right = boost::math::max_prime + 1; while (right - left > 1) { auto mid = (left + right) / 2; (boost::math::prime(mid) <= n ? left : right) = mid; } return n == boost::math::prime(left);*/ } #endif // INCLUDED_BOOST_PRIME // trial T tried = 3; #ifdef INCLUDED_BOOST_PRIME const int primes_size = boost::math::max_prime + 1; #else // INCLUDED_BOOST_PRIME const std::array primes = { 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, }; const int primes_size = primes.size(); #endif // INCLUDED_BOOST_PRIM for (int i = 2; i < primes_size; i++) { #ifdef INCLUDED_BOOST_PRIME const auto prime_i = boost::math::prime(i); #else // INCLUDED_BOOST_PRIME const auto prime_i = primes[i]; #endif // INCLUDED_BOOST_PRIM if (prime_i > n / prime_i) return true; if (n % prime_i == 0) { return false; } tried = prime_i; } const T n_sqrt = std::sqrt(n); for (T i = (tried + 5) / 6 * 6; i <= n_sqrt; i += 6) { if (n % (i - 1) == 0 || n % (i + 1) == 0) { return false; } } return true; } // input template inline auto input(T &&target) -> T { #if __cplusplus >= 202002L if constexpr (IsInputable) { std::cin >> target; } else if constexpr (IsEachable) { for (auto &&target_i : target) input(target_i); } else if constexpr (IsPair) { input(target.first); input(target.second); } else { // skip } #else // C++20 std::cin >> target; #endif // C++20 return target; } // input and initialize struct Scanner { template inline operator T() const { T target; return input(target); } } scan; // TODO: output // TODO: dump for debug /// main #if !defined(__INCLUDE_LEVEL__) || __INCLUDE_LEVEL__ <= 1 inline void cp_main(); int main() { using namespace std; using namespace std::chrono; # ifdef DEBUG cerr << "[INFO] running in debug mode!" << endl; const auto start = system_clock::now(); try { # endif // DEBUG cin.tie(nullptr); ios_base::sync_with_stdio(false); cout << fixed << setprecision(8); // run!!! cp_main(); # ifdef DEBUG cout << endl; } catch (exception e) { cout << endl; cerr << "[ERROR] " << e.what() << endl; } const auto end = system_clock::now(); const auto time_ms = duration_cast(end - start).count(); cerr << "[INFO] finished in " << time_ms << " ms!" << endl; # endif // DEBUG return 0; } #endif // __INCLUDE_LEVEL__ /// aliases using namespace std; #ifdef INCLUDED_ACL using namespace atcoder; #endif // INCLUDED_ACL using i64 = long long int; #endif // INCLUDED_MAIN