結果
問題 | No.308 素数は通れません |
ユーザー |
![]() |
提出日時 | 2015-12-01 12:45:16 |
言語 | Python3 (3.13.1 + numpy 2.2.1 + scipy 1.14.1) |
結果 |
AC
|
実行時間 | 34 ms / 1,000 ms |
コード長 | 964 bytes |
コンパイル時間 | 201 ms |
コンパイル使用メモリ | 12,544 KB |
実行使用メモリ | 11,264 KB |
最終ジャッジ日時 | 2024-11-27 18:09:58 |
合計ジャッジ時間 | 5,757 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 107 |
ソースコード
i=int(input()) import random def is_prime3(q,k=50): q = abs(q) #計算するまでもなく判定できるものははじく if q == 2: return True if q < 2 or q&1 == 0: return False #n-1=2^s*dとし(但しaは整数、dは奇数)、dを求める d = (q-1)>>1 while d&1 == 0: d >>= 1 #判定をk回繰り返す for i in range(k): a = random.randint(1,q-1) t = d y = pow(a,t,q) #[0,s-1]の範囲すべてをチェック while t != q-1 and y != 1 and y != q-1: y = pow(y,2,q) t <<= 1 if y != q-1 and t&1 == 0: return False return True if i==4: print(3) elif i==6: print(5) elif i==8 or i==9 or i== 10 or i==15 or i==16 or i==22: print(7) elif i==12: print(11) elif i==14: print(13) elif i==20 or i==21: print(19) elif i==24 or i==25: print(23) elif (i - 1) % 8 == 0 and is_prime3(i - 8): print(14) else: print(8)