結果

問題 No.308 素数は通れません
コンテスト
ユーザー ゴリポン先生
提出日時 2026-09-11 20:38:30
言語 D
(dmd 2.113.0)
コンパイル:
dmd -fPIE -m64 -w -wi -O -release -inline -I/opt/dmd/src/druntime/import/ -I/opt/dmd/src/phobos -L-L/opt/dmd/linux/lib64/ -fPIC _filename_
実行:
./Main
結果
AC  
実行時間 1 ms / 1,000 ms
+ 945µs
コード長 1,962 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 3,779 ms
コンパイル使用メモリ 195,328 KB
実行使用メモリ 6,528 KB
最終ジャッジ日時 2026-09-11 20:38:47
合計ジャッジ時間 7,674 ms
ジャッジサーバーID
（参考情報） 		judge2_0 / judge3_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 107
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

module main;
// https://kmjp.hatenablog.jp/entry/2015/12/02/0900 より
// 2次元グリッド
import std;

// https://drken1215.hatenablog.com/entry/2023/05/23/233000 より
// A ^^ N mod M
T powMod(T)(T A, T N, T M) {
	T res = 1 % M;
	A %= M;
	while (N) {
		if (N & 1) res = (res * A) % M;
		A = (A * A) % M;
		N >>= 1;
	}
	return res;
}
// ミラー–ラビン素数判定法
bool millerRabin(T)(T N, long[] A)
{
	if (N == 2)
		return true;
	if (N <= 1 || N % 2 == 0)
		return false;
	long s = 0;
	T d = N - 1;
	while ((d & 1) == 0) {
		++s;
		d >>= 1;
	}
	foreach (a; A) {
		if (N <= a) return true;
		long t;
		T x = powMod!T(T(a), d, N); // @suppress(dscanner.confusing.argument_parameter_mismatch)
		if (x == 1) continue;
		for (t = 0; t < s; ++t) {
			if (x == N - 1) break;
			x = x * x % N;
		}
		if (t == s) return false;
	}
	return true;
}
// エラトステネスの篩によってn以下の素数の表を返す
bool[] isPrime;
void sieve(int n)
{
	isPrime = [true].replicate(n + 1);
	isPrime[0] = isPrime[1] = false;
	for (int i = 2; i*i <= n; ++i)
		if (isPrime[i])
			for (int j = i*i; j <= n; j += i)
				isPrime[j] = false;
}

void main()
{
	// 入力
	auto N = BigInt(readln.chomp);
	// 答えの計算と出力
	if (N <= 10_000) {
		int n = cast(int)N;
		sieve(n);
		foreach (w; 2 .. n) {
			// 幅優先探索
			auto que = DList!int(1);
			auto seen = new bool[](n + 1);
			while (!que.empty) {
				int cur = que.removeAny;
				foreach (to; [cur - 1, cur + 1, cur - w, cur + w]) {
					if (cur % w == 1 && to == cur - 1)
						continue;
					if (cur % w == 0 && to == cur + 1)
						continue;
					if (to <= 0 || to > n)
						continue;
					if (!isPrime[to] && !seen[to]) {
						seen[to] = true;
						que.insertFront(to);
					}
				}
			}
			if (seen[n]) {
				writeln(w);
				return;
			}
		}
	} else {
		if (N % 8 == 1 && millerRabin(N - 8, [2L, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37]))
			writeln(14);
		else
			writeln(8);
	}
}
0