結果

問題 No.1653 Squarefree
ユーザー tktk_snsntktk_snsn
提出日時 2021-08-20 22:48:25
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 425 ms / 2,000 ms
コード長 1,029 bytes
コンパイル時間 172 ms
コンパイル使用メモリ 81,536 KB
実行使用メモリ 230,528 KB
最終ジャッジ日時 2024-10-14 08:26:29
合計ジャッジ時間 16,140 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 412 ms
230,400 KB
testcase_01 AC 240 ms
222,336 KB
testcase_02 AC 237 ms
222,464 KB
testcase_03 AC 240 ms
222,336 KB
testcase_04 AC 241 ms
222,336 KB
testcase_05 AC 243 ms
222,080 KB
testcase_06 AC 238 ms
222,336 KB
testcase_07 AC 235 ms
222,336 KB
testcase_08 AC 237 ms
222,080 KB
testcase_09 AC 236 ms
222,080 KB
testcase_10 AC 241 ms
222,080 KB
testcase_11 AC 320 ms
230,528 KB
testcase_12 AC 324 ms
230,400 KB
testcase_13 AC 403 ms
230,016 KB
testcase_14 AC 422 ms
230,400 KB
testcase_15 AC 420 ms
230,144 KB
testcase_16 AC 420 ms
230,144 KB
testcase_17 AC 424 ms
230,400 KB
testcase_18 AC 416 ms
230,144 KB
testcase_19 AC 411 ms
230,148 KB
testcase_20 AC 414 ms
230,400 KB
testcase_21 AC 407 ms
230,144 KB
testcase_22 AC 425 ms
230,528 KB
testcase_23 AC 415 ms
230,144 KB
testcase_24 AC 413 ms
230,400 KB
testcase_25 AC 408 ms
230,400 KB
testcase_26 AC 418 ms
230,272 KB
testcase_27 AC 410 ms
230,528 KB
testcase_28 AC 416 ms
230,400 KB
testcase_29 AC 413 ms
230,272 KB
testcase_30 AC 422 ms
230,016 KB
testcase_31 AC 408 ms
230,272 KB
testcase_32 AC 414 ms
230,144 KB
testcase_33 AC 418 ms
230,208 KB
testcase_34 AC 409 ms
230,144 KB
testcase_35 AC 419 ms
229,888 KB
testcase_36 AC 241 ms
222,336 KB
testcase_37 AC 241 ms
222,208 KB
testcase_38 AC 242 ms
222,336 KB
testcase_39 AC 238 ms
222,336 KB
testcase_40 AC 242 ms
222,080 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

from itertools import chain
U = 10 ** 6


def issqrt(n):
    nsq = int(n ** 0.5)
    for i in range(-2, 3):
        if (nsq+i)**2 == n:
            return True
    return False


def prime_set(N):
    """
    Nまでの素数のsetを返す
    """
    if N < 4:
        return ({}, {}, {2}, {2, 3})[N]
    Nsq = int(N ** 0.5 + 0.5) + 1
    primes = {2, 3} | set(chain(range(5, N + 1, 6), range(7, N + 1, 6)))
    for i in range(5, Nsq, 2):
        if i in primes:
            primes -= set(range(i * i, N + 1, i * 2))
    return primes


L, R = map(int, input().split())
N = R - L + 1
X = list(range(L, R+1))
primes = prime_set(U+10)

for p in primes:
    i = ((L + p - 1) // p) * p
    while i - L < N:
        cnt = 0
        if X[i-L] == -1:
            pass
        elif X[i-L] % (p*p) == 0:
            X[i-L] = -1
        else:
            X[i-L] //= p
        i += p

ans = 0
for x in X:
    if x == -1:
        continue
    if x == 1:
        ans += 1
        continue
    if not issqrt(x):
        ans += 1

print(ans)
0