test/math/is-prime/yosupo-Primality-Test.test.cpp

• View this file on GitHub
• Last update: 2023-07-30 19:34:47+08:00
• Problem: https://judge.yosupo.jp/problem/primality_test

Depends on

• library/math/is-prime.hpp
• library/math/pow-mod.hpp
• library/math/safe-mod.hpp
• library/misc/type-traits.hpp

Code

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

#include <iostream>
#include "../../../library/math/is-prime.hpp"
using namespace std;
using namespace felix;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	int q;
	cin >> q;
	while(q--) {
		long long n;
		cin >> n;
		cout << (is_prime(n) ? "Yes" : "No") << "\n";
	}
	return 0;
}

#line 1 "test/math/is-prime/yosupo-Primality-Test.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/primality_test"

#include <iostream>
#line 2 "library/math/is-prime.hpp"
#include <vector>

#line 2 "library/misc/type-traits.hpp"
#include <cassert>

#include <numeric>

#include <type_traits>


namespace felix {

namespace internal {

#ifndef _MSC_VER
template<class T> using is_signed_int128 = typename std::conditional<std::is_same<T, __int128_t>::value || std::is_same<T, __int128>::value, std::true_type, std::false_type>::type;
template<class T> using is_unsigned_int128 = typename std::conditional<std::is_same<T, __uint128_t>::value || std::is_same<T, unsigned __int128>::value, std::true_type, std::false_type>::type;
template<class T> using make_unsigned_int128 = typename std::conditional<std::is_same<T, __int128_t>::value, __uint128_t, unsigned __int128>;
template<class T> using is_integral = typename std::conditional<std::is_integral<T>::value || is_signed_int128<T>::value || is_unsigned_int128<T>::value, std::true_type, std::false_type>::type;
template<class T> using is_signed_int = typename std::conditional<(is_integral<T>::value && std::is_signed<T>::value) || is_signed_int128<T>::value, std::true_type, std::false_type>::type;
template<class T> using is_unsigned_int = typename std::conditional<(is_integral<T>::value && std::is_unsigned<T>::value) || is_unsigned_int128<T>::value, std::true_type, std::false_type>::type;
template<class T> using to_unsigned = typename std::conditional<is_signed_int128<T>::value, make_unsigned_int128<T>, typename std::conditional<std::is_signed<T>::value, std::make_unsigned<T>, std::common_type<T>>::type>::type;
#else
template<class T> using is_integral = typename std::is_integral<T>;
template<class T> using is_signed_int = typename std::conditional<is_integral<T>::value && std::is_signed<T>::value, std::true_type, std::false_type>::type;
template<class T> using is_unsigned_int = typename std::conditional<is_integral<T>::value && std::is_unsigned<T>::value, std::true_type, std::false_type>::type;
template<class T> using to_unsigned = typename std::conditional<is_signed_int<T>::value, std::make_unsigned<T>, std::common_type<T>>::type;
#endif

template<class T> using is_signed_int_t = std::enable_if_t<is_signed_int<T>::value>;
template<class T> using is_unsigned_int_t = std::enable_if_t<is_unsigned_int<T>::value>;
template<class T> using to_unsigned_t = typename to_unsigned<T>::type;

template<class T> struct safely_multipliable {};
template<> struct safely_multipliable<short> { using type = int; };
template<> struct safely_multipliable<unsigned short> { using type = unsigned int; };
template<> struct safely_multipliable<int> { using type = long long; };
template<> struct safely_multipliable<unsigned int> { using type = unsigned long long; };
template<> struct safely_multipliable<long long> { using type = __int128; };
template<> struct safely_multipliable<unsigned long long> { using type = __uint128_t; };

template<class T> using safely_multipliable_t = typename safely_multipliable<T>::type;

}  // namespace internal


}  // namespace felix

#line 2 "library/math/safe-mod.hpp"

namespace felix {

namespace internal {

template<class T>
constexpr T safe_mod(T x, T m) {
	x %= m;
	if(x < 0) {
		x += m;
	}
	return x;
}

} // namespace internal


} // namespace felix
#line 4 "library/math/pow-mod.hpp"

namespace felix {

namespace internal {

template<class T>
constexpr T pow_mod_constexpr(T x, long long n, T m) {
	using U = safely_multipliable_t<T>;
	if(m == 1) {
		return 0;
	}
	U r = 1, y = safe_mod(x, m);
	while(n) {
		if(n & 1) {
			r = (r * y) % m;
		}
		y = (y * y) % m;
		n >>= 1;
	}
	return r;
}

} // namespace internal


} // namespace felix

#line 4 "library/math/is-prime.hpp"

namespace felix {

namespace internal {

bool miller_rabin(long long n, std::vector<long long> x) {
	long long d = n - 1;
	d >>= __builtin_ctzll(d);
	for(auto a : x) {
		if(n <= a) {
			return true;
		}
		long long t = d;
		__uint128_t y = pow_mod_constexpr(a, d, n);
		while(t != n - 1 && y != 1 && y != n - 1ULL) {
			y = y * y % n;
			t <<= 1;
		}
		if(y != n - 1ULL && t % 2 == 0) {
			return false;
		}
	}
	return true;
}

} // namespace internal


bool is_prime(long long n) {
	if(n <= 1) {
		return false;
	}
	for(int p : {2, 3, 5, 7, 11, 13, 17, 19, 23, 29}) {
		if(n % p == 0) {
			return n == p;
		}
	}
	if(n < (1LL << 30)) {
		return internal::miller_rabin(n, {2, 7, 61});
	}
	return internal::miller_rabin(n, {2, 325, 9375, 28178, 450775, 9780504, 1795265022});
}

} // namespace felix

#line 5 "test/math/is-prime/yosupo-Primality-Test.test.cpp"
using namespace std;
using namespace felix;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	int q;
	cin >> q;
	while(q--) {
		long long n;
		cin >> n;
		cout << (is_prime(n) ? "Yes" : "No") << "\n";
	}
	return 0;
}

Back to top page