#61865 (Python2) No.308 素数は通れません

提出ソース

結果

問題	No.308 素数は通れません
ユーザー	tjake
提出日時	2015-12-01 21:23:39
言語	Python2 (2.7.18)
結果	WA
実行時間	-
コード長	1,264 bytes
コンパイル時間	439 ms
コンパイル使用メモリ	6,748 KB
実行使用メモリ	9,468 KB
最終ジャッジ日時	2023-10-12 07:10:39
合計ジャッジ時間	7,223 ms
ジャッジサーバーID （参考情報）	judge11 / judge15

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	16 ms 9,100 KB
testcase_01	AC	16 ms 9,368 KB
testcase_02	AC	18 ms 9,272 KB
testcase_03	AC	16 ms 9,108 KB
testcase_04	AC	15 ms 9,292 KB
testcase_05	AC	16 ms 9,108 KB
testcase_06	AC	16 ms 9,100 KB
testcase_07	AC	16 ms 9,108 KB
testcase_08	AC	16 ms 9,288 KB
testcase_09	AC	16 ms 9,144 KB
testcase_10	AC	18 ms 9,236 KB
testcase_11	AC	16 ms 9,116 KB
testcase_12	AC	16 ms 9,096 KB
testcase_13	AC	15 ms 9,160 KB
testcase_14	AC	15 ms 9,164 KB
testcase_15	AC	16 ms 9,096 KB
testcase_16	AC	16 ms 9,108 KB
testcase_17	AC	16 ms 9,144 KB
testcase_18	AC	16 ms 9,164 KB
testcase_19	AC	16 ms 9,136 KB
testcase_20	AC	15 ms 9,164 KB
testcase_21	AC	15 ms 9,144 KB
testcase_22	AC	15 ms 9,292 KB
testcase_23	AC	16 ms 9,136 KB
testcase_24	AC	16 ms 9,144 KB
testcase_25	AC	16 ms 9,240 KB
testcase_26	AC	16 ms 9,092 KB
testcase_27	AC	15 ms 9,112 KB
testcase_28	AC	16 ms 9,276 KB
testcase_29	AC	16 ms 9,148 KB
testcase_30	AC	17 ms 9,356 KB
testcase_31	AC	16 ms 9,156 KB
testcase_32	AC	16 ms 9,240 KB
testcase_33	AC	16 ms 9,240 KB
testcase_34	AC	16 ms 9,144 KB
testcase_35	AC	16 ms 9,148 KB
testcase_36	AC	18 ms 9,156 KB
testcase_37	AC	18 ms 9,132 KB
testcase_38	AC	18 ms 9,316 KB
testcase_39	AC	18 ms 9,384 KB
testcase_40	AC	18 ms 9,264 KB
testcase_41	AC	20 ms 9,184 KB
testcase_42	AC	19 ms 9,148 KB
testcase_43	AC	19 ms 9,328 KB
testcase_44	AC	19 ms 9,152 KB
testcase_45	AC	20 ms 9,160 KB
testcase_46	AC	20 ms 9,200 KB
testcase_47	AC	21 ms 9,208 KB
testcase_48	AC	21 ms 9,164 KB
testcase_49	AC	23 ms 9,264 KB
testcase_50	AC	24 ms 9,244 KB
testcase_51	AC	25 ms 9,248 KB
testcase_52	AC	29 ms 9,444 KB
testcase_53	AC	29 ms 9,268 KB
testcase_54	AC	30 ms 9,412 KB
testcase_55	AC	31 ms 9,216 KB
testcase_56	AC	18 ms 9,352 KB
testcase_57	AC	19 ms 9,240 KB
testcase_58	AC	17 ms 9,372 KB
testcase_59	AC	18 ms 9,252 KB
testcase_60	AC	17 ms 9,252 KB
testcase_61	AC	17 ms 9,220 KB
testcase_62	AC	17 ms 9,220 KB
testcase_63	AC	17 ms 9,248 KB
testcase_64	AC	141 ms 9,252 KB
testcase_65	AC	18 ms 9,372 KB
testcase_66	AC	18 ms 9,420 KB
testcase_67	AC	17 ms 9,468 KB
testcase_68	AC	18 ms 9,452 KB
testcase_69	AC	18 ms 9,248 KB
testcase_70	AC	271 ms 9,352 KB
testcase_71	AC	18 ms 9,224 KB
testcase_72	AC	18 ms 9,448 KB
testcase_73	AC	19 ms 9,448 KB
testcase_74	AC	18 ms 9,448 KB
testcase_75	AC	18 ms 9,388 KB
testcase_76	AC	37 ms 9,360 KB
testcase_77	AC	18 ms 9,432 KB
testcase_78	AC	18 ms 9,376 KB
testcase_79	AC	17 ms 9,400 KB
testcase_80	AC	40 ms 9,392 KB
testcase_81	AC	113 ms 9,276 KB
testcase_82	AC	18 ms 9,372 KB
testcase_83	AC	18 ms 9,376 KB
testcase_84	AC	126 ms 9,380 KB
testcase_85	AC	18 ms 9,216 KB
testcase_86	AC	144 ms 9,244 KB
testcase_87	AC	158 ms 9,200 KB
testcase_88	AC	18 ms 9,388 KB
testcase_89	AC	18 ms 9,376 KB
testcase_90	AC	229 ms 9,276 KB
testcase_91	AC	19 ms 9,428 KB
testcase_92	AC	17 ms 9,208 KB
testcase_93	AC	19 ms 9,248 KB
testcase_94	AC	19 ms 9,268 KB
testcase_95	AC	18 ms 9,384 KB
testcase_96	AC	17 ms 9,196 KB
testcase_97	AC	18 ms 9,396 KB
testcase_98	AC	18 ms 9,264 KB
testcase_99	AC	18 ms 9,448 KB
testcase_100	WA	-
testcase_101	AC	248 ms 9,216 KB
testcase_102	AC	18 ms 9,400 KB
testcase_103	AC	17 ms 9,272 KB
testcase_104	AC	18 ms 9,448 KB
testcase_105	AC	18 ms 9,248 KB
testcase_106	AC	18 ms 9,256 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

from random import randint
from collections import deque
from math import sqrt
n = input()

M = min(10003, n)
prime = [1]*(M+1)
prime[0] = prime[1] = 0
p_num = 0
for i in xrange(2, int(sqrt(M))+1):
    if prime[i]:
        for j in xrange(i*i, M+1, i):
            prime[j] = 0

def fermat(k):
    for t in xrange(10000):
        a = randint(2, k-1)
        if pow(a, k-1, k)!=1:
            return 0
    return 1

i = 2
while i<=40:
    deq = deque()
    deq.append(1)
    used = [0]*(M+1)
    ok = 0
    while deq:
        v = deq.popleft()
        if n>M and v%i==0:
            ok = 1
            break
        if v==n:
            print i
            exit(0)
        if v+1 <= M and v%i!=0 and not prime[v+1] and not used[v+1]:
            used[v+1] = 1
            deq.append(v+1)
        if v-1 >= 1 and v%i!=1 and not prime[v-1] and not used[v-1]:
            used[v-1] = 1
            deq.append(v-1)
        if v+i <= M and not prime[v+i] and not used[v+i]:
            used[v+i] = 1
            deq.append(v+i)
        if v-i >= 1 and not prime[v-i] and not used[v-i]:
            used[v-i] = 1
            deq.append(v-i)
    if ok:
        if (n%i!=1 and not fermat(n-1)) or not fermat(n-i):
            print i
            exit(0)
    i += 1
exit(1)

yukicoder

結果

テストケース

ソースコード