結果
問題 |
No.36 素数が嫌い!
|
ユーザー |
![]() |
提出日時 | 2020-02-11 23:35:12 |
言語 | Python3 (3.13.1 + numpy 2.2.1 + scipy 1.14.1) |
結果 |
WA
|
実行時間 | - |
コード長 | 674 bytes |
コンパイル時間 | 223 ms |
コンパイル使用メモリ | 12,544 KB |
実行使用メモリ | 11,392 KB |
最終ジャッジ日時 | 2024-10-01 11:58:11 |
合計ジャッジ時間 | 2,184 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 17 WA * 9 |
ソースコード
n=int(input()) def is_prime(n,k=50): import random # nが素数かを高速で判定 n = abs(n) if n==2: return True if n<2 or n&1==0: return False # ミラー・ラビンテストというらしい ちゃんと理解してないので要復習 d=(n-1)>>1 while d&1==0: d>>=1 for i in range(k): a=random.randint(1,n-1) t=d y=pow(a,t,n) while t!=n-1 and y!=1 and y!=n-1: y=pow(y,2,n) t<<=1 if y!=n-1 and t&1==0: return False return True if n==1: print('NO') else: if is_prime(n): print('NO') else: print('YES')