結果

問題 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
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 38
権限があれば一括ダウンロードができます

ソースコード

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