Felix's Library
This documentation is automatically generated by online-judge-tools/verification-helper
library/math/is-prime.hpp
- View this file on GitHub
- Last update: 2023-07-30 19:34:47+08:00
- Include:
#include "library/math/is-prime.hpp"
Depends on
library/math/safe-mod.hpp
Required by
Verified with
- test/math/factorize/aoj-ntl-Prime-Factorize.test.cpp
- test/math/factorize/yosupo-Factorize.test.cpp
- test/math/is-prime/yosupo-Primality-Test.test.cpp
Code
#pragma once
#include <vector>
#include "pow-mod.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 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