結果
問題 |
No.1653 Squarefree
|
ユーザー |
![]() |
提出日時 | 2021-08-20 23:56:55 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 569 ms / 2,000 ms |
コード長 | 1,486 bytes |
コンパイル時間 | 196 ms |
コンパイル使用メモリ | 82,392 KB |
実行使用メモリ | 133,760 KB |
最終ジャッジ日時 | 2024-10-14 08:42:34 |
合計ジャッジ時間 | 18,706 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 38 |
ソースコード
""" 素数の積で表せる L以上R以下を全探索出来る… 10^6以下の素数に関しては、全部塗りつぶせる logなので 残りは… 10^6以下の素数に関しては割り切ってもらっちゃおう すると、 平方数しかありえなくなる あとはやるだけ """ import sys from sys import stdin def Sieve(n): ret = [] divlis = [-1] * (n+1) flag = [True] * (n+1) flag[0] = False flag[1] = False ind = 2 while ind <= n: if flag[ind]: ret.append(ind) ind2 = ind ** 2 while ind2 <= n: flag[ind2] = False divlis[ind2] = ind ind2 += ind ind += 1 return ret,divlis plis,tmp = Sieve(2000000) L,R = map(int,stdin.readline().split()) lis = [i for i in range(L,R+1)] flag = [True] * (R-L+1) for p in plis: fi = ((L-1)//p + 1) * p find = fi-L assert fi-p < L #print (p,fi) for i in range(find,R-L+1,p): ns = 0 while flag[i] and lis[i] % p == 0: lis[i] //= p ns += 1 if ns > 1: flag[i] = False #print (lis) ans = 0 for i in range(R-L+1): if flag[i]: if lis[i] == 1: ans += 1 else: x = lis[i] y = int(x**0.5) if x not in ( (y-3)**2 , (y-2)**2 , (y-1)**2 , y**2 , (y+1)**2 , (y+2)**2 , (y+3)**2 ): ans += 1 print (ans)