結果

問題 No.1653 Squarefree
ユーザー tktk_snsntktk_snsn
提出日時 2021-08-20 22:48:25
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 468 ms / 2,000 ms
コード長 1,029 bytes
コンパイル時間 221 ms
コンパイル使用メモリ 82,288 KB
実行使用メモリ 230,740 KB
最終ジャッジ日時 2024-04-22 09:13:06
合計ジャッジ時間 17,137 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 468 ms
230,456 KB
testcase_01 AC 244 ms
222,444 KB
testcase_02 AC 243 ms
222,472 KB
testcase_03 AC 247 ms
222,572 KB
testcase_04 AC 243 ms
222,568 KB
testcase_05 AC 242 ms
222,332 KB
testcase_06 AC 239 ms
222,616 KB
testcase_07 AC 239 ms
222,532 KB
testcase_08 AC 241 ms
222,532 KB
testcase_09 AC 250 ms
222,424 KB
testcase_10 AC 239 ms
222,228 KB
testcase_11 AC 352 ms
230,412 KB
testcase_12 AC 352 ms
230,636 KB
testcase_13 AC 445 ms
230,240 KB
testcase_14 AC 453 ms
230,084 KB
testcase_15 AC 451 ms
230,560 KB
testcase_16 AC 456 ms
230,296 KB
testcase_17 AC 455 ms
230,296 KB
testcase_18 AC 460 ms
230,220 KB
testcase_19 AC 457 ms
230,556 KB
testcase_20 AC 455 ms
230,028 KB
testcase_21 AC 444 ms
230,456 KB
testcase_22 AC 454 ms
230,408 KB
testcase_23 AC 458 ms
230,348 KB
testcase_24 AC 462 ms
230,516 KB
testcase_25 AC 463 ms
230,732 KB
testcase_26 AC 442 ms
230,296 KB
testcase_27 AC 450 ms
230,384 KB
testcase_28 AC 456 ms
230,184 KB
testcase_29 AC 451 ms
230,740 KB
testcase_30 AC 454 ms
230,412 KB
testcase_31 AC 453 ms
230,344 KB
testcase_32 AC 458 ms
230,248 KB
testcase_33 AC 453 ms
230,156 KB
testcase_34 AC 448 ms
230,720 KB
testcase_35 AC 454 ms
230,300 KB
testcase_36 AC 241 ms
222,740 KB
testcase_37 AC 245 ms
222,332 KB
testcase_38 AC 245 ms
222,780 KB
testcase_39 AC 240 ms
222,508 KB
testcase_40 AC 240 ms
222,368 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