素数判定 (O(log(N))) (daylight/math/primality_test.hpp)

• View this file on GitHub
• Last update: 2024-12-26 20:32:55+09:00
• Include: #include "daylight/math/primality_test.hpp"

Depends on

• 基本テンプレート (daylight/base.hpp)
• 繰り返し2乗法でa^p mod mを求める (daylight/math/powmod.hpp)

Required by

• 素因数分解をO(N^(1/4))で行う (daylight/math/rho.hpp)

Verified with

• test/aoj/ntl/1_A.test.2.cpp
• test/aoj/others/1276.test.2.cpp
• test/yosupo/number_theory/factorize.test.cpp
• test/yosupo/number_theory/primality_test.test.cpp

Code

#include "daylight/base.hpp"
#include "daylight/math/powmod.hpp"

/// @brief 素数判定 (O(log(N)))
bool is_prime(ll N) {
	if(N == 2) return true;
	if(N == 1 || N % 2 == 0) return false;
	ll s = 0;
	ll d = N - 1;
	while(d % 2 == 0) {
		s++;
		d /= 2;
	}
	vll tests
		= { 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37 };
	for(auto a: tests) {
		if(a == N) continue;
		ll X = pow_mod(a, d, N);
		int r = 0;
		if(X == 1) {
			continue;
		}
		while(X != N - 1) {
			X = pow_mod(X, 2, N);
			r++;
			if(X == 1 || r == s) return false;
		}
	}
	return true;
}

Traceback (most recent call last):
  File "/home/runner/.local/lib/python3.10/site-packages/competitive_verifier/oj_resolve/resolver.py", line 181, in resolve
    bundled_code = language.bundle(path, basedir=basedir)
  File "/home/runner/.local/lib/python3.10/site-packages/competitive_verifier/oj/verify/languages/cplusplus.py", line 252, in bundle
    bundler.update(path)
  File "/home/runner/.local/lib/python3.10/site-packages/competitive_verifier/oj/verify/languages/cplusplus_bundle.py", line 482, in update
    self.update(
  File "/home/runner/.local/lib/python3.10/site-packages/competitive_verifier/oj/verify/languages/cplusplus_bundle.py", line 477, in update
    raise BundleErrorAt(
competitive_verifier.oj.verify.languages.cplusplus_bundle.BundleErrorAt: daylight/base.hpp: line 103: unable to process #include in #if / #ifdef / #ifndef other than include guards

Back to top page