Lこんにちは、ぐぐりら(@guglilac)です。結局解けたけどTLE一回してしまったので、復習。Nが素数で、(N+1)/2も素数であるN(=2017に似た数)の個数を求める問題。クエリがQ個与えられる。素数のリストを得る必要がある。クエリの区間の最大(右端)は問題設定から$10^5$なので、$10^5$以下の素数のリストが得られればよい。愚直に素数かを判定して素数ならリストにいれるというのでは遅いので、エラトステネスの篩を使う。これで素数のリストが得られる。次に2017に似た数を列挙して個数を数える。判定は定義の通りやればいいけれど、うっかりすると計算量が多くなるので注意しないといけない。すると、毎回primesを全部見て素数であるかを調べてしまう。$10^5$だと素数のリストは10000個ぐらいあったので、$10^8$ぐらいになってしまって間に合わない。自然数$x$が素数かどうかをO(1)で調べられるようにフラグで管理する。いう書き方がすぐできるようになりたい。list:`みたいな書き方が簡単だし見やすいから書いてしまう。累積和を先に計算しておいて、左端を右端から引けばいい、みたいなやつです。区間といわれるとこれかな?となるようになってきました。`C[x]`を$x$以下の2017に似た数の個数として求めていきます。Blogger.ぐぐりらにっきQooQ。