#1185865 (D) No.308 素数は通れません

• 問題: No.308 素数は通れません
• ユーザー: ゴリポン先生
• 提出日時: 2026-09-11 14:18:03
• 言語: D (dmd 2.113.0)
• 結果: WA
• 実行時間: -
• コード長: 3,008 bytes
• コンパイル時間: 5,024 ms
• コンパイル使用メモリ: 195,216 KB
• 実行使用メモリ: 9,992 KB
• 最終ジャッジ日時: 2026-09-11 14:18:22
• 合計ジャッジ時間: 9,462 ms
• ジャッジサーバーID （参考情報）: judge1_0 / judge3_0

ファイルパターン	結果
other	AC * 103 WA * 4

ソースコード

module main;
// https://yukicoder.me/problems/no/308/editorial より
// 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;
}
// アトキンのふるい
bool[] isPrime;
void sieveOfAtkin(int N)
{
	isPrime = new bool[](N + 1);
	int sqrtN = cast(int)sqrt(cast(double)N);
	int n;
	foreach (z; [1, 5]) {
		for (int y = z; y <= sqrtN; y += 6) {
			for (int x = 1; x <= sqrtN && (n = 4*x*x + y*y) <= N; ++x)
				isPrime[n] = !isPrime[n];
			for (int x = y + 1; x <= sqrtN && (n = 3*x*x - y*y) <= N; x += 2)
				isPrime[n] = !isPrime[n];
		}
	}
	foreach (z; [2, 4]) {
		for (int y = z; y < sqrtN; y += 6) {
			for (int x = 1; x <= sqrtN && (n = 3*x*x + y*y) <= N; x += 2)
				isPrime[n] = !isPrime[n];
		for (int x = y + 1; x <= sqrtN && (n = 3*x*x - y*y) <= N; x += 2)
			isPrime[n] = !isPrime[n];
		}
	}
	for (int y = 3; y <= sqrtN; y += 6) {
		foreach (z; [1, 2]) {
			for (int x = z; x <= sqrtN && (n = 4*x*x + y*y) <= N; x += 3)
				isPrime[n] = !isPrime[n];
		}
	}
	foreach (i; 5 .. sqrtN + 1)
		if (isPrime[i])
			for (int k = i*i; k <= N; k+=i*i)
				isPrime[k] = false;
	isPrime[2] = isPrime[3] = true;
}

void main()
{
	// 入力
	auto N = BigInt(readln.chomp);
	// 答えの計算と出力
	if (N <= 10_000) {
		int n = cast(int)N;
		sieveOfAtkin(n);
		foreach (w; 3 .. n) {
			if (isPrime[w + 1])
				continue;
			// 幅優先探索
			auto que = DList!int(1);
			auto seen = new bool[](n + 1);
			seen[1] = true;
			while (!que.empty) {
				int cur = que.removeAny;
				// 右
				if (cur % w != 0 && !isPrime[cur + 1] && !seen[cur + 1]) {
					if (cur + 1 == n) {
						writeln(w);
						return;
					}
					seen[cur + 1] = true;
					que.insertFront(cur + 1);
				}
				// 左
				if (cur % w != 1 && !isPrime[cur - 1] && !seen[cur - 1]) {
					seen[cur - 1] = true;
					que.insertFront(cur - 1);
				}
				// 下
				if (cur + w <= n && !isPrime[cur + w]) {
					if (cur + w == n) {
						writeln(w);
						return;
					}
					seen[cur + w] = true;
					que.insertFront(cur + w);
				}
				// 上
				if (cur - w > 0 && !isPrime[cur - w] && !seen[cur - w]) {
					seen[cur - w] = true;
					que.insertFront(cur - w);
				}
			}
		}
	} 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);
	}
}