結果

問題 No.36 素数が嫌い！
コンテスト
ユーザー matrie
提出日時 2020-12-22 07:30:11
言語 Python3
(3.13.1 + numpy 2.2.1 + scipy 1.14.1)
結果
WA  
実行時間 -
コード長 600 bytes
コンパイル時間 112 ms
コンパイル使用メモリ 12,800 KB
実行使用メモリ 369,920 KB
最終ジャッジ日時 2024-09-21 13:44:15
合計ジャッジ時間 8,618 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample -- * 4
other WA * 1 TLE * 1 -- * 24
権限があれば一括ダウンロードができます

ソースコード

diff # 

import random

def f(n):
	if n == 2: return True
	if n == 1 or n & 1 == 0: return False
	d = (n - 1) >> 1
	while d & 1 == 0: d >>= 1
	for k in range(100):
		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 = (y * y) % n
			t <<= 1
		if y != n - 1 and t & 1 == 0:
			return False
	return True

def c(x):
	l=list(range(2,int(x**.5)+1))+[x]
	t=0
	while len(l)>0 and l[-1]==x:
		t=l[0]
		print(t)
		l=[i for i in l if i%t>0]
	return t
	
s="NO"
n=int(input())
fn=f(n);
if fn: print("NO")
else:
	a=c(n);
	b=c(n//a)
	print("YES" if a*b<n else "NO")
0