結果
問題 | No.1653 Squarefree |
ユーザー |
|
提出日時 | 2022-03-12 11:49:01 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 438 ms / 2,000 ms |
コード長 | 761 bytes |
コンパイル時間 | 300 ms |
コンパイル使用メモリ | 82,304 KB |
実行使用メモリ | 92,544 KB |
最終ジャッジ日時 | 2024-09-16 17:31:32 |
合計ジャッジ時間 | 13,828 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 38 |
ソースコード
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 start * start == xans = 0for i in d:if i == 0:continueif i == 1:ans += 1continueif check(i) == False:ans += 1print(ans)