結果

問題 No.308 素数は通れません
コンテスト
ユーザー titia
提出日時 2026-06-28 05:04:31
言語 PyPy3
(7.3.17)
コンパイル:
pypy3 -mpy_compile _filename_
実行:
pypy3 _filename_
結果
AC  
実行時間 150 ms / 1,000 ms
コード長 2,931 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 284 ms
コンパイル使用メモリ 85,504 KB
実行使用メモリ 134,680 KB
最終ジャッジ日時 2026-06-28 05:05:10
合計ジャッジ時間 10,003 ms
ジャッジサーバーID
（参考情報） 		judge3_1 / judge1_1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 107
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

import sys
input = sys.stdin.readline


# https://qiita.com/t_fuki/items/7cd50de54d3c5d063b4a#%E3%83%9F%E3%83%A9%E3%83%BC%E3%83%A9%E3%83%93%E3%83%B3%E7%B4%A0%E6%95%B0%E5%88%A4%E5%AE%9A%E6%B3%95%E3%81%AE%E3%82%A2%E3%83%AB%E3%82%B4%E3%83%AA%E3%82%BA%E3%83%A0
def is_prime(n):
    if n == 2:  # 2であれば素数なので終了
        return 1
    if n == 1 or n%2 == 0:  # 1もしくは2より大きい偶数であれば素数でないので終了
        return 0

    m = n - 1
    lsb = m & -m  # LSB. m-1をビット列で表した時立っているビットのうち最も小さいもの
    s = lsb.bit_length()-1  # 上述のs. LSB以上のビットの部分をdとし、2^s = LSBとすると上述のp-1 = 2^sdを満たす
    d = m // lsb

    test_numbers = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37]

    for a in test_numbers:
        if a == n:  # a = n -> 任意の自然数kについてa^k ≡ 0(mod n)なので無視
            continue
        x = pow(a,d,n)  # x ≡ a^d(mod n)で初期化
        r = 0
        if x == 1:  # a^d ≡ 1(mod n)なので無視
            continue
        while x != m:  # r = 0からsまで順にx ≡ a^(2^rd) ≡ -1(mod n)を検証
            x = pow(x,2,n)
            r += 1
            if x == 1 or r == s:  # x ≡ 1(mod n) -> x^2 ≡ 1(mod n)で-1になり得ないので合成数
                return 0
    return 1  # すべてのテストを通過したら素数であるとして終了

x=10**6   

L=1000

Primelist=[i for i in range(x+1)]
Primelist[1]=0 # 1は素数でないので0にする.
 
for i in Primelist:
    if i>L:
        break
    if i==0:
        continue
    for j in range(2*i,x+1,i):
        Primelist[j]=0

Primes=[Primelist[j] for j in range(x+1) if Primelist[j]!=0]

SP=set(Primes)

N=int(input())

if N<=10**6:
    for w in range(1,N+1):
        h=(N+w-1)//w

        MAP=[[0]*w for i in range(h)]
        MAP[0][0]=1
        Q=[(0,0)]
        r=N%w
        if r==0:
            r=w

        while Q:
            x,y=Q.pop()

            for z0,w0 in [(x+1,y),(x-1,y),(x,y+1),(x,y-1)]:
                if 0<=z0<h and 0<=w0<w:
                    if z0!=h-1:
                        if (z0*w+w0+1) in SP:
                            continue
                        else:
                            if MAP[z0][w0]==0:
                                MAP[z0][w0]=1
                                Q.append((z0,w0))
                    else:
                        if 0<=w0<r:
                            if (z0*w+w0+1) in SP:
                                continue
                            else:
                                if MAP[z0][w0]==0:
                                    MAP[z0][w0]=1
                                    Q.append((z0,w0))

        if MAP[h-1][r-1]==1:
            print(w)
            break
                            

else:
    if N%8==1 and is_prime(N-8):
        print(14)
    else:
        print(8)
0