Problem:


Score : 400 points

Problem Statement

We say that a odd number N is similar to 2017 when both N and (N+1)/2 are prime.

You are given Q queries.

In the i-th query, given two odd numbers l_i and r_i, find the number of odd numbers x similar to 2017 such that l_i ≤ x ≤ r_i.

Constraints

1≤Q≤10^5

1≤l_i≤r_i≤10^5

l_i and r_i are odd.

All input values are integers.

Input

Input is given from Standard Input in the following format:

Q
l_1 r_1
:
l_Q r_Q

Output

Print Q lines. The i-th line (1≤i≤Q) should contain the response to the i-th query.

Sample Input 1

1
3 7

Sample Output 1

2

3 is similar to 2017, since both 3 and (3+1)/2=2 are prime.

5 is similar to 2017, since both 5 and (5+1)/2=3 are prime.

7 is not similar to 2017, since (7+1)/2=4 is not prime, although 7 is prime.

Thus, the response to the first query should be 2.

Sample Input 2

4
13 13
7 11
7 11
2017 2017

Sample Output 2

1
0
0
1

Note that 2017 is also similar to 2017.

Sample Input 3

6
1 53
13 91
37 55
19 51
73 91
13 49

Sample Output 3

4
4
1
1
1
2



Sample input:
1
3 7


Sample output:
2

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

def isPrime_np(n):
    maxp = int(np.sqrt(n))
    searchlist = [i for i in range(2,n+1)]
    primeNum = []

    while searchlist[0] <= maxp:
        primeNum.append(searchlist[0])
        tmp = searchlist[0]
        searchlist = [i for i in searchlist if i % tmp != 0]
    primeNum.extend(searchlist)
    
    return primeNum

Q = int(input())

a = [0]*10**5
ans = []

prime = isPrime_np(10**5)
pset = set(prime)

for i in range(Q):
    l,r = map(int,input().split())
    for p in prime:
        if p>r:
            break
        if (p+1)/2 in pset:
            a[p] = 1
    ans.append(sum(a[l:r+1]))

print(*ans,sep="\n")

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

def isPrime_np(n):
    maxp = int(np.sqrt(n))
    searchlist = [i for i in range(2,n+1)]
    primeNum = []

    while searchlist[0] <= maxp:
        primeNum.append(searchlist[0])
        tmp = searchlist[0]
        searchlist = [i for i in searchlist if i % tmp != 0]
    primeNum.extend(searchlist)
    
    return primeNum

Q = int(input())

a = [0]*10**5
ans = []

for i in range(Q):
    l,r = map(int,input().split())
    prime = isPrime_np(r)
    pset = set(prime)
    for p in prime:
        if (p+1)/2 in pset:
            a[p] = 1
    ans.append(sum(a[l:r+1]))

print(*ans,sep="\n")

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
q = int(input())


p_max = 10**5+1
m = np.zeros(p_max, dtype=int)
for i in range(2, p_max):
    m[::i] += 1
# print(m)
ans = []
for _ in range(q):
    cnt = 0
    l, r = map(int, input().split())
    for i in range(l, r+1, 2):
        if m[i] == 1 and m[(i+1)//2] == 1:
            cnt += 1
    ans.append(cnt)


for i in range(q):
    print(ans[i])

Submission status: Time Limit Exceeded

Solution code:
q = int(input())


def isPrime(n):
    if n == 1:
        return 0
    if n == 2:
        return 1
    if n % 2 == 0:
        return 0
    m = int(n**0.5)+1
    for p in range(3, m, 2):
        if n % p == 0:
            return 0
    return 1


prime = [0]*(10**5+1)
for i in range(1, 10**5+1, 2):
    prime[i] = isPrime(i) & isPrime((i+1)//2)
# print(prime)

ans = []
for _ in range(q):
    l, r = map(int, input().split())
    cnt = sum(prime[l:r+1])
    ans.append(cnt)


for i in range(q):
    print(ans[i])

Submission status: Time Limit Exceeded

Solution code:
def main():
    q = int(input())
    
    
    def isPrime(n):
        if n == 1:
            return False
        if n == 2:
            return True
        if n % 2 == 0:
            return False
        m = int(n**0.5)+1
        for p in range(3, m, 2):
            if n % p == 0:
                return False
        return True
    
    
    ans = []
    for _ in range(q):
        l, r = map(int, input().split())
        cnt = 0
        for i in range(l, r+1, 2):
            if isPrime(i) and isPrime((i+1)//2):
                cnt += 1
        ans.append(cnt)
    
    for i in range(q):
        print(ans[i])

main()

Submission status: Time Limit Exceeded

Solution code:
q = int(input())


def isPrime(n):
    if n == 1:
        return False
    if n == 2:
        return True
    if n % 2 == 0:
        return False
    m = int(n**0.5)+1
    for p in range(3, m, 2):
        if n % p == 0:
            return False
    return True


ans = []
for _ in range(q):
    l, r = map(int, input().split())
    cnt = 0
    for i in range(l, r+1, 2):
        if isPrime(i) and isPrime((i+1)//2):
            cnt += 1
    ans.append(cnt)

for i in range(q):
    print(ans[i])

Submission status: Time Limit Exceeded

Solution code:

import math
N=int(input())

n=110000
count=0
isprime=[True]*(n+1)
isprime[0]=False
isprime[1]=False
for i in range(2,int(math.sqrt(n))+1):
    if isprime[i]==True:
        j=i+i
        while j<=n:
            isprime[j] =False
            j=j+i
for k in range(N):
    l,r=map(int,input().split())
    count=0
    for i in range(l,r+1):
        if isprime[i]==True:
            if isprime[(i+1)//2]==True:
                count+=1
    print(count)

Submission status: Time Limit Exceeded

Solution code:

import math
N=int(input())
S=[]
def eratos(n,l,r):
    count=0
    isprime=[True]*(n+1)
    isprime[0]=False
    isprime[1]=False
    for i in range(2,int(math.sqrt(n))+1):
        if isprime[i]==True:
            j=i+i
            while j<=n:
                isprime[j] =False
                j=j+i

    for i in range(l,r+1):
        if isprime[i]==True:
            if isprime[(i+1)//2]==True:
                count+=1
    
    return count
    
for k in range(N):
    l,r=map(int,input().split())

    print(eratos(110000,l,r))

Submission status: Time Limit Exceeded

Solution code:

import math
N=int(input())
S=[]
def eratos(n):
    isprime=[True]*(n+1)
    isprime[0]=False
    isprime[1]=False
    for i in range(2,int(math.sqrt(n))+1):
        if isprime[i]==True:
            j=i+i
            while j<=n:
                isprime[j] =False
                j=j+i

    for i in range(n+1):
        if isprime[i]==True:
            S.append(i)
    
    return S
    

T=eratos(110000)

for k in range(N):
    count=0
    l,r=map(int,input().split())

    for i in range(l,r+1):
        if i in T:
            if (i+1)//2 in T:
                count+=1
    print(count)

Submission status: Time Limit Exceeded

Solution code:
q = int(input())
l,r = [],[]
for i in range(q):
    li,ri = map(int,input().split())
    l.append(li)
    r.append(ri)

tmp = [0 for i in range(10**5+1)]
#tmp[2]=1
sosu = [2]
for i in range(3,max(r)+1,2):
    for j in sosu:
        if i%j==0:
            break
    else:
        sosu.append(i)
        tmp[i]=1

for kazu in range(min(l),max(r)+1,2):
    if not(kazu in sosu and (kazu+1)//2 in sosu):
        tmp[kazu]=0
#print(tmp[:1000])

for i in range(q):
    print(sum(tmp[l[i]:r[i]+1]))

Submission status: Time Limit Exceeded

Solution code:
q = int(input())
l,r = [],[]
for i in range(q):
    li,ri = map(int,input().split())
    l.append(li)
    r.append(ri)

tmp = [0 for i in range(10**5+1)]
tmp[2]=1
sosu = [2]
for i in range(3,max(r)+1,2):
    for j in sosu:
        if i%j==0:
            break
    else:
        sosu.append(i)
        tmp[i]=1

for i in range(q):
    cnt = 0
    for kazu in range(l[i],r[i]+1,2):
        if tmp[kazu]==1 and tmp[(kazu+1)//2]==1:
            cnt += 1
    print(cnt)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
def isP(x):
    for i in range(2,int(np.sqrt(x))+1):
        if x % i == 0:
            return False
    return True

#クエリにO(1)で返すためのテーブルを用意
MAX = int(10e5+1)
P = [isP(x) for x in range(MAX)]
Ans = [0] * MAX
cnt = 0
for i in range(1,MAX):
    if P[i] and P[(i+1)//2]:
        cnt += 1
    Ans[i] = cnt

q = int(input())
for i in range(q):
    l, r = map(int, input().split())
    print(Ans[r]-Ans[l-1])

Submission status: Time Limit Exceeded

Solution code:
def prime(n):
    if n==1:
        return False
    flag=True
    for i in range(2,int(n**0.5)+1):
        if n%i==0:
            flag=False
    return flag

Q=int(input())
L=[0]*Q
for _ in range(Q):
    l,r=list(map(int, input().split()))
    ct=0
    for i in range(l,r+1,2):
        n,m=i,(i+1)//2
        flag=prime(n)&prime(m)
        ct+=flag
    L[_]=ct
for _ in range(Q):
    print(L[_])

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

def seachPrimeNum(N):
    max = int(np.sqrt(N))
    seachList = [i for i in range(2,N+1)]
    primeNum = []
    while seachList[0] <= max:
        primeNum.append(seachList[0])
        tmp = seachList[0]
        seachList = [i for i in seachList if i % tmp != 0]
    primeNum.extend(seachList)
    return primeNum

#def numsearch(list):
    #for i in list:
        #print(i)
        #if (i+1)/2 not in list:
            #list.remove(i)
    #return list

def main():
    Q = int(input())
    list = seachPrimeNum(100000)
    #list2 = numsearch(list)
    #print(list2)
    c = [0]*100001
    c[0] = 0
    for i in range(1,100001,1):
        #print(i)
        if i in list and (i+1)/2 in list:
            c[i] = c[i-1]+1
        else:
            c[i] = c[i-1]
    #print(c)
    for i in range(Q):
        l,r = map(int,input().split())
        print(c[r]-c[l-1])

main()

Submission status: Time Limit Exceeded

Solution code:
def LI():
    return list(map(int, input().split()))


Q = int(input())
n = 10**5
sosu = set(range(2, n+1))
for i in range(2, int(n**0.5+1)):
    sosu.difference_update(range(i*2, n+1, i))
sosu = list(sosu)
for _ in range(Q):
    ans = 0
    L, R = LI()
    for i in range(L, R+1, 2):
        if i in sosu:
            if (i+1)//2 in sosu:
                ans += 1
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
import math
def eratosthenes(n):
    prime_list = []
    num_list=[i for i in range(2, n+1)]
    limit = math.sqrt(n)
    while True:
        if limit <= num_list[0]:
            return prime_list + num_list
        prime_list.append(num_list[0])
        num_list = [e for e in num_list if e % num_list[0] != 0]
        
Q = int(input())
for i in range(Q):
    l, r = input().split()
    l = int(l)
    R = eratosthenes(int(r))
    row = []
    for j in R:
        if j in R and j >= l:
           row.append(j)
    cnt = 0
    for k in row:
      if (k + 1) / 2 in R:
        cnt+=1
    print(cnt)

Submission status: Time Limit Exceeded

Solution code:
def isPrime(num):
    if num < 2:
        return False
    elif num == 2:
        return True
    elif num % 2 == 0:
        return False

    for i in range(3, int(num**0.5)+1, 2):
        if num % i == 0:
            return False
    return True

def is_2017(num):
    temp = (num + 1) // 2
    if isPrime(num) and isPrime(temp):
        return True
    else:
        return False

if __name__ == "__main__":
        
    Q = int(input())
    l_r = [tuple(map(int, input().split())) for _ in range(Q)]
    answer_list = []
    for l, r in l_r:
        count = 0
        for i in range(l, r+1, 2):
            count += is_2017(i)
        answer_list.append(count)

    for ans in answer_list:
        print(ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy
x=int(input())
n=10**5
import math
def eratosthenes(n):
    prime = []
    limit = math.sqrt(n)
    data = [i + 1 for i in range(1, n)]
    while True:
        p = data[0]
        if limit <= p:
            return prime + data
        prime.append(p)
        data = [e for e in data if e % p != 0]
q=eratosthenes(n)

ans1=[0]*(10**5+1)
for i in range(10**5+1):
    ans1[i]=(1 if i in q and (i+1)//2 in q else 0 )

ans=numpy.cumsum(ans1)
for i in range(x):
    l,r = map(int,input().split())	
    print(ans[r]-ans[l-1])

Submission status: Time Limit Exceeded

Solution code:
def primes(n):
    is_prime = [True] * (n + 1)
    is_prime[0] = False
    is_prime[1] = False
    for i in range(2, int(n**0.5) + 1):
        if not is_prime[i]:
            continue
        for j in range(i * 2, n + 1, i):
            is_prime[j] = False
    return [1 if i%2 and is_prime[i] and is_prime[(i+1)//2] else 0 for i in range(n+1)]

p=primes(10**5)

Q=int(input())
for _ in range(Q):
    l,r=map(int,input().split())
    print(sum(p[l:r+1]))

Submission status: Time Limit Exceeded

Solution code:
def primes(n):
    is_prime = [True] * (n + 1)
    is_prime[0] = False
    is_prime[1] = False
    for i in range(2, int(n**0.5) + 1):
        if not is_prime[i]:
            continue
        for j in range(i * 2, n + 1, i):
            is_prime[j] = False
    return [1 if i%2 and (i+1)//2>=0 and is_prime[i] and is_prime[(i+1)//2] else 0 for i in range(n+1)]

p=primes(10**5)

Q=int(input())
for _ in range(Q):
    l,r=map(int,input().split())
    print(sum(p[l:r+1]))

Submission status: Time Limit Exceeded

Solution code:
x=int(input())
n=10**5
import math
def eratosthenes(n):
    prime = []
    limit = math.sqrt(n)
    data = [i + 1 for i in range(1, n)]
    while True:
        p = data[0]
        if limit <= p:
            return prime + data
        prime.append(p)
        data = [e for e in data if e % p != 0]
q=eratosthenes(n)

ans=[0]*(10**5+1)
for i in range(10**5):
    ans[i+1]=ans[i]+(1 if i+1 in q and (i+1+1)//2 in q else 0 )
for i in range(x):
    l,r = map(int,input().split())	
    print(ans[r]-ans[l-1])

Submission status: Time Limit Exceeded

Solution code:
x=int(input())
n=10**5
def sieve(n):
    is_prime = [True for _ in range(n+1)]
    is_prime[0] = False

    for i in range(2, n+1):
        if is_prime[i-1]:
            j = 2 * i
            while j <= n:
                is_prime[j-1] = False
                j += i
    table = [ i for i in range(1, n+1) if is_prime[i-1]]
    return  table
q=sieve(n)
ans=[0]*(10**5+1)
for i in range(10**5):
    ans[i+1]=ans[i]+(1 if i+1 in q and (i+1+1)//2 in q else 0 )
for i in range(x):
    l,r = map(int,input().split())	
    print(ans[r]-ans[l-1])

Submission status: Time Limit Exceeded

Solution code:
x=int(input())
a=list(range(2,100000))
for i in  range(len(a)):
    for k in range(len(a)):
        if  a[i]<a[k] and a[i]!=0 and a[k]%a[i]==0:
            a[k]=0
#以上までで合成数を0にした2から99のリストができる
##print([i for i in a if i!=0])
#↑これで0を除ける．むずいね
q=[i for i in a if i!=0]
ans=[0]*(10**5+1)
for i in range(10**5):
    ans[i+1]=ans[i]+(1 if i+1 in q and (i+1+1)//2 in q else 0 )
for i in range(x):
    l,r = map(int,input().split())	
    print(ans[r]-ans[l-1])

Submission status: Time Limit Exceeded

Solution code:
import math

q = int(input())
odds_list = [[0]*2 for _ in range(q)]
max_odd = 0
for i in range(q):
    odds_list[i][0],odds_list[i][1] = map(int,input().split())
    max_odd = max(max_odd,odds_list[i][0],odds_list[i][1])
pn=[2]
m = math.floor(math.sqrt(max_odd)) + 1
for L in range(3,m,2):
    chk=True
    for L2 in pn:
        if L%L2 == 0:chk=False
    if chk:pn.append(L)

def isPrime(n):
  if n == 2:
    return True
  if n % 2 == 0:
    return False

  m = math.floor(math.sqrt(n))
  for p in pn:
      if n % p == 0:
        return False
      if p > m:
        # 素数がnの平方根を超えたら終了
        break
  return True

for k in range(q):
    count =0
    l = odds_list[k][0]
    r = odds_list[k][1]
    for j in range(l,r+1,2):
        if j ==1:
            continue
        if isPrime(j) and isPrime((j+1)/2):
            count +=1
    print(count)

Submission status: Time Limit Exceeded

Solution code:
import sys


def solve(l, r, primeset):
    res = 0
    for i in range(l, r + 1, 2):
        if i in primeset and (i + 1) // 2 in primeset:
            res += 1
    return res


input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)


def main():
    primelist = [2]
    A = 10 ** 5 + 10
    for L in range(3, A, 2):
        if all(L % L2 != 0 for L2 in primelist):
            primelist.append(L)
    primeset = set(primelist)
    # print(primelist[:20])
    Q = int(input())
    for i in range(Q):
        l, r = map(int, input().split())
        print(solve(l, r, primeset))


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys


def isprime(x):
    # 素数判定
    if x == 2:
        return True
    if x < 2 or x % 2 == 0:
        return False
    i = 3
    while i <= x ** 0.5:
        if x % i == 0:
            return False
        i += 2
    return True


def solve(l, r, primelist, primelist2):
    res = 0
    for i in range(l, r + 1, 2):
        if primelist[i] and primelist2[i]:
            res += 1
    return res


input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)


def main():
    primelist = [False] * (10 ** 5 + 10)
    primelist2 = [False] * (10 ** 5 + 10)
    primelist[2] = True
    for i in range(1, 10 ** 5 + 1, 2):
        if isprime(i):
            primelist[i] = True
    for i in range(1, 10 ** 5 + 1, 2):
        if primelist[(i + 1) // 2]:
            primelist2[i] = True
    # print(primelist[:20])
    Q = int(input())
    for i in range(Q):
        l, r = map(int, input().split())
        print(solve(l, r, primelist, primelist2))


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys


def isprime(x):
    # 素数判定
    if x == 2:
        return True
    if x < 2 or x % 2 == 0:
        return False
    i = 3
    while i <= x ** 0.5:
        if x % i == 0:
            return False
        i += 2
    return True


def solve(l, r, primelist, primelist2):
    res = 0
    for i in range(l, r + 1, 2):
        if primelist[i] and primelist2[i]:
            res += 1
    return res


input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)


def main():
    primelist = [False] * (10 ** 5 + 10)
    primelist2 = [False] * (10 ** 5 + 10)
    primelist[2] = True
    for i in range(1, 10 ** 5 + 1, 2):
        if isprime(i):
            primelist[i] = True
        if isprime((i + 1) // 2):
            primelist2[i] = True
    # print(primelist[:20])
    Q = int(input())
    for i in range(Q):
        l, r = map(int, input().split())
        print(solve(l, r, primelist, primelist2))


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys


def isprime(x):
    # 素数判定
    if x == 2:
        return True
    if x < 2 or x % 2 == 0:
        return False
    i = 3
    while i <= x ** 0.5:
        if x % i == 0:
            return False
        i += 2
    return True


def solve(l, r, primelist):
    res = 0
    for i in range(l, r + 1, 2):
        if primelist[i] and primelist[(i + 1) // 2]:
            res += 1
    return res


input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)


def main():
    primelist = [False] * (10 ** 5 + 10)
    primelist[2] = True
    for i in range(1, 10 ** 5 + 1, 2):
        if isprime(i):
            primelist[i] = True
    # print(primelist[:20])
    Q = int(input())
    for i in range(Q):
        l, r = map(int, input().split())
        print(solve(l, r, primelist))


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import bisect
L = []
for _ in range(int(input())):
  a, b = map(int, input().split())
  a, b = (a-1)//2, (b-1)//2
  L.append([a,b])
X_1 = [i for i in range(2, 10**5+1)]
X_2 = []
while len(X_1)>0:
  X_2.append(X_1[0])
  X_1 = [x for x in X_1 if x%X_1[0] != 0]
T = [0]*(10**5)
for i in range(10**5-1):
  if bisect.bisect_left(X_2, 2*i+1)!=bisect.bisect_right(X_2, 2*i+1)\
  and bisect.bisect_left(X_2, i+1)!=bisect.bisect_right(X_2, i+1):
    T[i+1]=T[i]+1
  else:
    T[i+1]=T[i]
for l in L:
  print(T[l[1]+1]-T[l[0]])

Submission status: Time Limit Exceeded

Solution code:
def primes(n):
    is_prime = [True] * (n + 1)
    is_prime[0] = False
    is_prime[1] = False
    for i in range(2, int(n**0.5) + 1):
        if not is_prime[i]:
            continue
        for j in range(i * 2, n + 1, i):
            is_prime[j] = False
    
    like=[False]*(n+1)
    for i in range(1,n+1,2):
        if(is_prime[i]==False):
            continue
        else:
            if(is_prime[int((i+1)/2)]==True):
                like[i]=True
            
    return  like
    #return [i for i in range(n + 1) if is_prime[i]]
q=int(input())
table=primes(10**5+10)
for i in range(q):
    l,r=map(int,input().split())
    accum=[0]
    for i in range(1,r+2):
        if(table[i]==True):
            accum.append(accum[i-1]+1)
        else:
            accum.append(accum[i-1])
    print(accum[r]-accum[l-1])

Submission status: Time Limit Exceeded

Solution code:
def prime_eratosthenes(n):
    prime_list = []
    num_list=[]
    for i in range(2, n+1):
        if i not in num_list:
            prime_list.append(i)
            for j in range(i*i, n+1, i):
                num_list.append(j)
    return prime_list

ls = prime_eratosthenes(100000)
ls2 = [i+1 for i in range(100000)]
Q = int(input())
for i in range(Q):
    l, r = map(int, input().split())
    ans = 0
    for j in range(l-1, r):
        if (ls2[j] in ls) and (ls2[j+1]//2 in ls):
            ans += 1
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
def prime_eratosthenes(n):
    prime_list = []
    num_list=[]
    for i in range(2, n+1):
        if i not in num_list:
            prime_list.append(i)
            for j in range(i*i, n+1, i):
                num_list.append(j)
    return prime_list

ls = prime_eratosthenes(100000)
ls2 = [i+1 for i in range(100000)]
print(ls2)
Q = int(input())
for i in range(Q):
    l, r = map(int, input().split())
    ans = 0
    for j in range(l-1, r):
        if (ls2[j] in ls) and (ls2[j+1]//2 in ls):
            ans += 1
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
import math
def s(n):
    for c in range(2,int(math.sqrt(n)+1)):
        if n%c==0:
            return False
    if n==1:
        return False
    return True
q=int(input())
lr = [map(int, input().split()) for _ in range(q)]
l, r = [list(i) for i in zip(*lr)]
k=[]
for i in range(q):
    k.append(0)
    for j in range(l[i],r[i]+1):
        if s(j)==True :
            if s(int((j+1)/2))==True:
                k[i]=k[i]+1
    print(k[i])

Submission status: Time Limit Exceeded

Solution code:
import math
def get_prime(n):
    if n<=1:
      return []
    prime=[2]
    limit=int(math.sqrt(n))
    
    data=[i+1 for i in range(2,n,2)]
    while limit>data[0]:
      prime.append(data[0])
      
      data=[j for j in data if j % data[0]!=0]
      
    return prime+data

xx=get_prime(100000)

xxx=[False]*100001

for i in xx:
  xxx[i]=True

xxxx=[False]*100001

for i in xx:
  xxxx[i]=True

for i in range(1,100001):
  if xxx[i]==True:
    if xxxx[(i+1)//2]==False:
      xxx[i]=False

q=int(input())

for i in range(q):
  l,r=map(int,input().split())
  print(sum(xxx[:r+1])-sum(xxx[:l]))

Submission status: Time Limit Exceeded

Solution code:
#-----------------------------------
#リストera_list[n]を返す
#0～ｎの各インデックスが素数であれば1、そうでなければ0
#ex：eratosthenes(10)
#　　→ [0, 0, 1, 1, 0, 1, 0, 1, 0, 0, 0]
#-----------------------------------

def eratosthenes(n):
  era_list = [1] * (n + 1)
  era_list[0] = 0; era_list[1] = 0
  
  for i in range(2,n+1):
    if era_list[i] == 0:
      continue
    else:
      j = i + i
      while j <= n:
        era_list[j] = 0
        j += i
        
  return era_list

Q = int(input())
PN = eratosthenes(100001)
TF = [0] * 100001

for i in range(1,100001,2):
  if PN[i] == 1 and PN[int((i+1)/2)] == 1:
    TF[i] = 1
    
for j in range(1,Q+1):
  l,r = map(int, input().split())
  Ans = sum(TF[:r+1]) - sum(TF[:l])
  print(Ans)

Submission status: Time Limit Exceeded

Solution code:
import sys

def input():
    return sys.stdin.readline().strip()

def main():

    Q = int(input())
    ma = 10 ** 5 + 1
    dp = [0] * ma
    dp[2] = 1

    for i in range(3,ma,2):
        if dp[i] == 0:
            dp[i] = 1
            if dp[(i + 1) // 2] == 1 or dp[(i + 1) // 2] == 2:
                dp[i] = 2
            for j in range(i * 2,ma,i):
                dp[j] = 3

    for _ in range(Q):
        l,r = map(int,input().split())
        print(dp[l:r+1].count(2))

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
Q = int(input())
ma = 10 ** 5 + 1
dp = [0] * ma
dp[2] = 1

for i in range(3,ma,2):
    if dp[i] == 0:
        dp[i] = 1
        if dp[(i + 1) // 2] == 1 or dp[(i + 1) // 2] == 2:
            dp[i] = 2
        for j in range(i * 2,ma,i):
            dp[j] = 3

for _ in range(Q):
    l,r = map(int,input().split())
    print(dp[l:r+1].count(2))

Submission status: Time Limit Exceeded

Solution code:
import math

def is_prime(n):
  if n == 1:
    return False
  if n%2 ==0:
    if n == 2:
      return True
    else:
      return False
  for i in range(3, int(math.sqrt(n)//1)+1, 2):
    if n%i == 0:
      return False
  return True

Q = int(input())
ans = []
for _ in range(Q):
  counter = 0
  l, r = map(int, input().split())
  for odd in range(l, r+1, 2):
    if is_prime(odd) and is_prime((odd+1)/2):
      counter += 1
  ans.append(counter)

for item in ans:
  print(item)

Submission status: Time Limit Exceeded

Solution code:
q = int(input())

n = 10**5+1
nums = [True]*n
nums[1] = False
for i in range(4, n, 2): nums[i] = False
for i in range(3, int(n**0.5)+1, 2):
  if nums[i]:
    for j in range(i+i, n, i): nums[j] = False

for _ in range(q):
  ans = 0
  l,r = map(int, input().split())
  for i in range(l, r+1,2):
    if nums[i] and nums[(i+1)//2]: ans += 1
  print(ans)

Submission status: Time Limit Exceeded

Solution code:
q = int(input())

n = 10**5+1
nums = [True]*n
nums[1] = False
for i in range(4, n, 2): nums[i] = False
for i in range(3, int(n**0.5)+1, 2):
  if nums[i]:
    for j in range(i+i, n, i): nums[j] = False

for _ in range(q):
  ans = 0
  l,r = map(int, input().split())
  for i in range(l, r+1):
    if i%2 == 1:
      if nums[i] and nums[(i+1)//2]: ans += 1
  print(ans)

Submission status: Time Limit Exceeded

Solution code:
Q = int(input())

ls = [list(map(int,input().split())) for i in range(Q)]
n_max = max(ls)[1]

prime = []
data = [i for i in range(2,n_max+1)]
limit = n_max**(1/2)
while True:
    p = data[0]
    if limit<=p:
        break
    prime.append(p)
    data = [i for i in data if i%p!=0]
prime = prime +data

ans_ls = [0]*len(prime)
for i in range(len(prime)):
    if (prime[i]+1)//2 in prime:
        ans_ls[i] =1

for l,r in ls:
    ans = 0
    for i in range(len(prime)):
        if (prime[i]>r):
            break
        elif (l<=prime[i]):
           ans += ans_ls[i]
            
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
Q = int(input())

ls = [list(map(int,input().split())) for i in range(Q)]
n_max = max(ls)[1]

prime = []
data = [i for i in range(2,n_max+1)]
limit = n_max**(1/2)
while True:
    p = data[0]
    if limit<=p:
        break
    prime.append(p)
    data = [i for i in data if i%p!=0]
prime = prime +data

ans_ls = [0]*len(prime)
for i in range(len(prime)):
    if (prime[i]+1)//2 in prime:
        ans_ls[i] =1

for l,r in ls:
    ans = 0
    for i in range(len(prime)):
        if (l<=prime[i]) and (prime[i]<=r):
           ans += ans_ls[i]
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
def seachPrimeNum(N):
  max = int(np.sqrt(N))
  seachList = [i for i in range(2,N+1)]
  primeNum = []
  while seachList[0] <= max:
    primeNum.append(seachList[0])
    tmp = seachList[0]
    seachList = [i for i in seachList if i % tmp != 0]
  primeNum.extend(seachList)
  return primeNum

n=10**5
a=seachPrimeNum(n)
b=[]
y=0
x=0
while x<=100000:
  t=a[y]
  x=t*2-1
  b.append(x)
  y+=1
  
c=set(a)&set(b)

q=int(input())
for p in range(q):
  ans=0
  w,z=map(int,input().split())
  for j in c:
    if w<=j<=z:
      ans+=1
    if j<w or z<j:
      continue
  print(ans)

Submission status: Time Limit Exceeded

Solution code:
import math
from math import gcd
INF = float("inf")

import sys
input=sys.stdin.readline
import itertools
from collections import Counter

def main():
    def isPrime(n):
        if n == 2:
            return True
        if n%2 == 0 or n == 1:
            return False
        m = math.floor(math.sqrt(n))+1
        for p in range(3,m,2):
            if n%p == 0:
                return False
        return True

    q = int(input())
    list = []
    for i in range(q):
        cnt = 0
        l,r = map(int, input().split())
        for k in range(l,r+1):
            if k != 2 and k%2==0:
                pass
            else:
                if isPrime(k) and isPrime((k+1)//2):
                    cnt += 1
        list.append(cnt)
    print("\n".join(map(str, list)))

if __name__=="__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
def sieve(n):
    is_prime =[True for i in range(n+1)]
    is_prime[0] = False
    is_prime[1] = False
    for i in range(2,int(n**0.5)+1):
        if is_prime[i]:
            for j in range(i+i,n,i):
                is_prime[j] = False
    c = [0 for i in range(n+1)]
    for i in range(3,n+1,2):
        if is_prime[i] and is_prime[(i+1)//2]:
            c[i] = 1
    for i in range(n):
        c[i+1] += c[i]
    return c

def solve(l,r,c):
    return c[r]-c[l-1]



if __name__ == '__main__':
    q = int(input())
    for i in range(q):
        l,r = map(int,input().split())
        c = sieve(100000)
        print(solve(l,r,c))

Submission status: Time Limit Exceeded

Solution code:
def sieve(n):
    is_prime =[True for i in range(n+1)]
    is_prime[0] = False
    is_prime[1] = False
    for i in range(2,n+1):
        if is_prime[i]:
            for j in range(i+i,n,i):
                is_prime[j] = False
    c = [0 for i in range(n+1)]
    for i in range(3,n+1,2):
        if is_prime[i] and is_prime[(i+1)//2]:
            c[i] = 1
    for i in range(n):
        c[i+1] += c[i]
    return c

def solve(l,r,c):
    return c[r]-c[l-1]



if __name__ == '__main__':
    q = int(input())
    for i in range(q):
        l,r = map(int,input().split())
        c = sieve(100000)
        print(solve(l,r,c))

Submission status: Time Limit Exceeded

Solution code:
def solve(l,r):
    p = 0
    is_prime =[True for i in range(r+1)]
    is_prime[0] = False
    is_prime[1] = False
    for i in range(2,r+1):
        if is_prime[i]:
            p += 1
            for j in range(i+i,r,i):
                is_prime[j] = False
    c = [0 for i in range(r+1)]
    for i in range(3,r+1,2):
        if is_prime[i] and is_prime[(i+1)//2]:
            c[i] = c[i-2] + 1
        else:
            c[i] = c[i-2]
    if l != 1:
        res = c[r] - c[l-2]
    else:
        res = c[r] - c[l]
    return res

if __name__ == '__main__':
    q = int(input())
    for i in range(q):
        l,r = map(int,input().split())
        print(solve(l,r))

Submission status: Time Limit Exceeded

Solution code:
def solve(l,r):
    prime = [True for i in range(r+1)]
    prime[0] = False
    prime[1] = False
    for i in range(2,int(r**0.5)+1):
        for j in range(2*i,r+1,i):
            prime[j] = False
    res = 0
    for i in range(l,r+1,2):
        if prime[i] and prime[(i+1)//2]:
            res += 1
    return res

if __name__ == '__main__':
    q = int(input())
    for i in range(q):
        l,r = map(int,input().split())
        print(solve(l,r))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

def seachPrimeNum(N):
    max = int(np.sqrt(N))
    seachList = [i for i in range(2,N+1)]
    primeNum = []
    while seachList[0] <= max:
        primeNum.append(seachList[0])
        tmp = seachList[0]
        seachList = [i for i in seachList if i % tmp != 0]
    primeNum.extend(seachList)
    return primeNum
L=seachPrimeNum(100000)
R=[i for i in L if (i+1)//2 in L]
Q=int(input())
for i in range(Q):
  a,b=map(int,input().split())
  print(len([i for i in R if i>=a and i<=b]))