結果

問題 No.1653 Squarefree
ユーザー ntuda
提出日時 2025-03-22 14:17:15
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 943 ms / 2,000 ms
コード長 1,061 bytes
コンパイル時間 217 ms
コンパイル使用メモリ 82,420 KB
実行使用メモリ 96,768 KB
最終ジャッジ日時 2025-03-22 14:17:51
合計ジャッジ時間 25,830 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 38
権限があれば一括ダウンロードができます

ソースコード

diff # 

L, R = map(int, input().split())
if R == 1:
    print(1)
    exit()

# 素数リスト作成
def PrimeList(N):
    P = [1] * (N + 1)
    P[0] = P[1] = 0
    for i in range(2, N + 1):
        if P[i]:
            for j in range(i + i, N + 1, i):
                P[j] = 0
    PL = []
    for i in range(N + 1):
        if P[i] == 1:
            PL.append(i)
    return PL

PL = PrimeList(10 ** 6)
A = list(range(L, R + 1))

for p in PL:
    p2 = p * p
    for i in range(-(-L // p) * p - L, R // p * p - L + 1, p):
        j = 0
        while A[i] % p == 0:
            if j == 1:
                A[i] = -1
            else:
                A[i] //= p
            j += 1

def check(x, y):
    return x >= y * y

for i in range(R - L + 1):
    a = A[i]
    if a > 1:
        lb = 0
        ub = R
        while ub - lb > 1:
            mid = (ub + lb) // 2
            if check(a, mid):
                lb = mid
            else:
                ub = mid
        if a == lb * lb:
            A[i] = -1
ans = 0
for a in A:
    if a > 0:
        ans += 1
print(ans)
0