AtCoder Beginner Contest 084 / D - 2017-like Number

解法

1. エラトステネスのふるいで、制約条件である100000までの素数表を作る (myo)
2. 1で作成した素数表をもとに、2017に似た数 表を作る (r2017)
3. r2017_ の累積和を取る (rodd)__
4. Qのクエリに rodd[$ r_{i+1} $] - rodd[ $l_i$ ] で答えていく。

def eratos(n :int):
    # initialize
    isprime = [True] * (n+1)
    isprime[0] = isprime[1] = False

    for i in range(2, int(math.sqrt(n)+1)):
        if(isprime[i]):
            j = i+i
            while(j <= n):
                isprime[j] = False
                j = j+i

    return isprime

def solve(Q: int, l: "List[int]", r: "List[int]"):
    myo = eratos(100000)
    rodd = [0]*100001

    r2017 = [False]*100001
    for i in range(1,100001):
        if(i%2 == 0):
            continue
        elif(myo[i] and myo[int((i+1)/2)]):
            r2017[i] = True

    for i in range(2,100001):
        rodd[i] = rodd[i-1] +(1 if r2017[i-1] else 0)

    ans = [0]*Q
    for i in range(Q):
        ans[i] = rodd[r[i]+1] - rodd[l[i]]

    for i in ans:
        print(i)

    return

参考

@drkenさんの神解説

qiita.com