Reference: M. Forisek and J. Jancina, Fast Primality Testing for Integers That Fit into a Machine Word @param n `0 <= n`
| 81 | // Fast Primality Testing for Integers That Fit into a Machine Word |
| 82 | // @param n `0 <= n` |
| 83 | constexpr bool is_prime_constexpr(int n) { |
| 84 | if (n <= 1) return false; |
| 85 | if (n == 2 || n == 7 || n == 61) return true; |
| 86 | if (n % 2 == 0) return false; |
| 87 | long long d = n - 1; |
| 88 | while (d % 2 == 0) d /= 2; |
| 89 | constexpr long long bases[3] = {2, 7, 61}; |
| 90 | for (long long a : bases) { |
| 91 | long long t = d; |
| 92 | long long y = pow_mod_constexpr(a, t, n); |
| 93 | while (t != n - 1 && y != 1 && y != n - 1) { |
| 94 | y = y * y % n; |
| 95 | t <<= 1; |
| 96 | } |
| 97 | if (y != n - 1 && t % 2 == 0) { |
| 98 | return false; |
| 99 | } |
| 100 | } |
| 101 | return true; |
| 102 | } |
| 103 | template <int n> constexpr bool is_prime = is_prime_constexpr(n); |
| 104 | |
| 105 | // @param b `1 <= b` |