結果
問題 | No.1653 Squarefree |
ユーザー |
|
提出日時 | 2022-03-12 11:46:12 |
言語 | PyPy3 (7.3.15) |
結果 |
WA
|
実行時間 | - |
コード長 | 757 bytes |
コンパイル時間 | 295 ms |
コンパイル使用メモリ | 82,144 KB |
実行使用メモリ | 92,612 KB |
最終ジャッジ日時 | 2024-09-16 17:27:21 |
合計ジャッジ時間 | 12,702 ms |
ジャッジサーバーID (参考情報) |
judge6 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 35 WA * 3 |
ソースコード
L,R = map(int,input().split())C = 10 ** 6dat = [0] * Cd = list(range(L,R+1))for i in range(2,C):if dat[i] == 0:for j in range(2 * i,C,i):dat[j] = 1for j in range((L+i-1)//i,R//i+1):d[i * j - L] //= inow = i * ifor j in range((L+now-1)//now,R//now+1):d[now*j-L] = 0def check(x):if x <= 10 ** 12:return Falsestart = 10 ** 6end = 10 ** 9 + 1while end - start > 1:mid = end + start >> 1if mid * mid <= x:start = midelse:end = midreturn mid * mid == xans = 0for i in d:if i == 0:continueif i == 1:ans += 1continueif check(i) == False:ans += 1print(ans)