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: Wrong Answer

Solution code:
import sys
import bisect
import math
input = sys.stdin.readline

n = int(input())
l = [list(map(int, input().split())) for _ in range(n)]

mc = max(l)[1]
mc_sqrt = math.sqrt(mc)

prime = [i for i in range(2, mc + 1)]
c = 0
while True:
    if c >= len(prime):
        break
    t = prime[c]
    prime = [v for v in prime if v == t or v % t != 0]
    c = c + 1
    if c >= mc_sqrt:
        break
        
cum = [0 for i in range(mc + 1)]
for i in range(len(cum)):
    prime_index = bisect.bisect_left(prime, i)
    
    n2 = (i + 1) / 2
    prime_index2 = bisect.bisect_left(prime, n2)
    if len(prime) > prime_index and len(prime) > prime_index2 and prime[prime_index] == i and prime[prime_index2] == n2:
        cum[i] = cum[i - 1] + 1
    else:
        if i - 1 < 0:
            cum[i] = 0
        else:
            cum[i] = cum[i - 1]

for t in l:
    x, y = t[0], t[1]
    p = 0
    if 0 <= x - 1:
        p = cum[x] - cum[x - 1]
    print(p)

Submission status: Wrong Answer

Solution code:
import sys
import bisect
import math
input = sys.stdin.readline

n = int(input())
l = [list(map(int, input().split())) for _ in range(n)]

mc = max(l)[1]
mc_sqrt = math.sqrt(mc)

prime = [i for i in range(2, mc + 1)]
c = 0
while True:
    if c >= len(prime):
        break
    t = prime[c]
    prime = [v for v in prime if v == t or v % t != 0]
    c = c + 1
    if c >= mc_sqrt:
        break
        
cum = [0 for i in range(mc + 1)]
for i in range(len(cum)):
    prime_index = bisect.bisect_left(prime, i)
    
    n2 = (i + 1) / 2
    prime_index2 = bisect.bisect_left(prime, n2)
    if len(prime) > prime_index and len(prime) > prime_index2 and prime[prime_index] == i and prime[prime_index2] == n2:
        cum[i] = cum[i - 1] + 1
    else:
        if i - 1 < 0:
            cum[i] = 0
        else:
            cum[i] = cum[i - 1]

for t in l:
    x, y = 0, 0
    p = 0
    if 0 <= x - 1:
        p = cum[x] - cum[x - 1]
    if x != y:
        p += cum[y] - cum[x]
    print(p)

Submission status: Wrong Answer

Solution code:
import sys
import bisect
import math
input = sys.stdin.readline

n = int(input())
l = [list(map(int, input().split())) for _ in range(n)]

mc = max(l)[1]
mc_sqrt = math.sqrt(mc)

prime = [i for i in range(2, mc + 1)]
c = 0
while True:
    if c >= len(prime):
        break
    t = prime[c]
    prime = [v for v in prime if v == t or v % t != 0]
    c = c + 1
    if c >= mc_sqrt:
        break
        
cum = [0 for i in range(mc + 1)]
for i in range(len(cum)):
    prime_index = bisect.bisect_left(prime, i)
    
    n2 = (i + 1) / 2
    prime_index2 = bisect.bisect_left(prime, n2)
    if len(prime) > prime_index and len(prime) > prime_index2 and prime[prime_index] == i and prime[prime_index2] == n2:
        cum[i] = cum[i - 1] + 1
    else:
        if i - 1 < 0:
            cum[i] = 0
        else:
            cum[i] = cum[i - 1]

for t in l:
    print(0)

Submission status: Wrong Answer

Solution code:
import sys
import bisect
import math
input = sys.stdin.readline

n = int(input())
l = [list(map(int, input().split())) for _ in range(n)]

mc = max(l)[1]
mc_sqrt = math.sqrt(mc)

prime = [i for i in range(2, mc + 1)]
c = 0
while True:
    if c >= len(prime):
        break
    t = prime[c]
    prime = [v for v in prime if v == t or v % t != 0]
    c = c + 1
    if c >= mc_sqrt:
        break
        
cum = [0 for i in range(mc + 1)]
for i in range(len(cum)):
    prime_index = bisect.bisect_left(prime, i)
    
    n2 = (i + 1) / 2
    prime_index2 = bisect.bisect_left(prime, n2)
    if len(prime) > prime_index and len(prime) > prime_index2 and prime[prime_index] == i and prime[prime_index2] == n2:
        cum[i] = cum[i - 1] + 1
    else:
        if i - 1 < 0:
            cum[i] = 0
        else:
            cum[i] = cum[i - 1]
            
sys.exit()
        
for x, y in l:
    p = cum[x] - cum[x - 1]
    if x != y:
        p += cum[y] - cum[x]
    print(p)

Submission status: Wrong Answer

Solution code:
import sys
import bisect
import math
input = sys.stdin.readline

n = int(input())
l = [list(map(int, input().split())) for _ in range(n)]

mc = max(l)[1]
mc_sqrt = math.sqrt(mc)

prime = [i for i in range(2, mc + 1)]
c = 0
while True:
    if c >= len(prime):
        break
    t = prime[c]
    prime = [v for v in prime if v == t or v % t != 0]
    c = c + 1
    if c >= mc_sqrt:
        break
        
sys.exit()
        
cum = [0 for i in range(mc + 1)]
for i in range(len(cum)):
    prime_index = bisect.bisect_left(prime, i)
    
    n2 = (i + 1) / 2
    prime_index2 = bisect.bisect_left(prime, n2)
    if len(prime) > prime_index and len(prime) > prime_index2 and prime[prime_index] == i and prime[prime_index2] == n2:
        cum[i] = cum[i - 1] + 1
    else:
        if i - 1 < 0:
            cum[i] = 0
        else:
            cum[i] = cum[i - 1]
        
for x, y in l:
    p = cum[x] - cum[x - 1]
    if x != y:
        p += cum[y] - cum[x]
    print(p)

Submission status: Wrong Answer

Solution code:
import sys
import bisect
import math
input = sys.stdin.readline

n = int(input())
l = [list(map(int, input().split())) for _ in range(n)]

mc = max(l)[1]
mc_sqrt = math.sqrt(mc)

sys.exit()

prime = [i for i in range(2, mc + 1)]
c = 0
while True:
    if c >= len(prime):
        break
    t = prime[c]
    prime = [v for v in prime if v == t or v % t != 0]
    c = c + 1
    if c >= mc_sqrt:
        break
        
cum = [0 for i in range(mc + 1)]
for i in range(len(cum)):
    prime_index = bisect.bisect_left(prime, i)
    
    n2 = (i + 1) / 2
    prime_index2 = bisect.bisect_left(prime, n2)
    if len(prime) > prime_index and len(prime) > prime_index2 and prime[prime_index] == i and prime[prime_index2] == n2:
        cum[i] = cum[i - 1] + 1
    else:
        if i - 1 < 0:
            cum[i] = 0
        else:
            cum[i] = cum[i - 1]
        
for x, y in l:
    p = cum[x] - cum[x - 1]
    if x != y:
        p += cum[y] - cum[x]
    print(p)

Submission status: Wrong Answer

Solution code:
MAX=100000
isprime=[1]*(MAX+1)
isprime[0]=0
isprime[1]=0

for i in range(2,int(pow(MAX,0.5)+1)):
    if isprime[i]==1:
        for j in range(i*2,MAX+1,i):
            isprime[j]=0

islike2017=[0]*(MAX)
for i in range(MAX):
    if isprime[i]==1 and isprime[int((i+1)/2)]==1:
        islike2017[i]=1

cumsum=[0]*(MAX+1)
for i in range(1,MAX+1):
    cumsum[i]=cumsum[i-1]+islike2017[i-1]

Q=int(input())
l=0
r=0
for i in range(Q):
    l, r = map(int, input().split())
    print(cumsum[r]-cumsum[l])

Submission status: Wrong Answer

Solution code:
import math

def eratosthenes(limit):
    A = [i for i in range(2, limit + 1)]
    B = []
    while True:
        a = min(A)
        if a > math.sqrt(limit):
            break
        B.append(a)
        i = 0
        while len(A) > i:
            if A[i] % a == 0:
                A.pop(i)
                continue
            i += 1
    for a in A:
        B.append(a)
    print(B)
    return B

def main():
    Q = int(input())
    lr = []
    mr = 0
    ans = []
    for _ in range(Q):
        l, r = map(int, input().split())
        lr.append((l, r))
        mr = max(mr, r)
    A = eratosthenes(mr)
    for l, r in lr:
        c = 0
        for i in range(l, r + 1, 2):
            if i in A and (i + 1) // 2 in A:
                c += 1
        ans.append(c)
    for c in ans:
        print(c)


main()

Submission status: Wrong Answer

Solution code:
q=int(input())
l=[0,0,0]
c=0
def prime(n):
  if n==2:
    return True
  elif n==1:
    return False
  else:
    return pow(2,n-1,n)==1
for i in range(3,100001):
  if prime(i)==True and prime((i+1)//2)==True:
    c+=1
  l.append(c)
for i in range(q):
  a,b=map(int,input().split())
  print(l[b]-l[a-1])

Submission status: Wrong Answer

Solution code:
q=int(input())
l=[]
c=0
def prime(n):
  if n==2:
    return True
  elif n==1:
    return False
  else:
    return pow(2,n-1,n)==1
for i in range(1,100001,2):
  if prime(i)==True and prime((i+1)//2)==True:
    c+=1
  l.append(c)
for i in range(q):
  a,b=map(int,input().split())
  print(l[b//2]-l[a//2])

Submission status: Wrong Answer

Solution code:
q=int(input())
l=[]
c=0
def prime(n):
  if n==2:
    return True
  elif n==1:
    return False
  else:
    return pow(2,n-1,n)==1
for i in range(1,200001,2):
  if prime(i)==True and prime((i+1)//2)==True:
    c+=1
  l.append(c)
for i in range(q):
  a,b=map(int,input().split())
  print(l[b//2]-l[max((a//2)-1,0)])

Submission status: Wrong Answer

Solution code:
q=int(input())
l=[]
c=0
def prime(n):
  if n==2:
    return True
  elif n==1:
    return False
  else:
    return pow(2,n-1,n)==1
for i in range(1,100001,2):
  if prime(i)==True and prime((i+1)//2)==True:
    c+=1
  l.append(c)
for i in range(q):
  a,b=map(int,input().split())
  print(l[b//2]-l[max((a//2)-1,0)])

Submission status: Wrong Answer

Solution code:
q=int(input())
l=[]
c=0
def prime(n):
  if n==2:
    return True
  elif n==1:
    return False
  else:
    return pow(2,n-1,n)==1
for i in range(1,100001,2):
  if prime(i)==True and prime((i+1)//2)==True:
    c+=1
  l.append(c)
for i in range(q):
  a,b=map(int,input().split())
  print(l[b//2]-l[(a//2)-1])

Submission status: Wrong Answer

Solution code:
q=int(input())
l=[]
c=0
def prime(n):
  if n==2:
    return True
  elif n==1:
    return False
  else:
    return pow(2,n-1,n)==1
for i in range(1,100001,2):
  if prime(i)==True and prime((i+1)//2)==True:
    c+=1
  l.append(c)
for i in range(q):
  a,b=map(int,input().split())
  print(l[b//2]-l[a//2-1])

Submission status: Wrong Answer

Solution code:
q=int(input())
l=[0]
c=0
def prime(n):
  if n==2:
    return True
  elif n==1:
    return False
  else:
    return pow(2,n-1,n)==1
for i in range(1,100001):
  if prime(i)==True and prime((i+1)//2)==True:
    c+=1
  l.append(c)
for i in range(q):
  a,b=map(int,input().split())
  print(l[b]-l[a-1])

Submission status: Wrong Answer

Solution code:
def isPrime(n):
    for p in primes:
        if n%p == 0:
            return False
        elif n < p*p:
            return True

primes = [2,3,5,7]
for i in range(11,10**5,2):
    if isPrime(i):
        primes.append(i)
n2017s = [0]
for p in primes[1:]:
    if (p+1)//2 in primes:
        n2017s.append(p)

def binary_search(n):
    l=0
    r=len(n2017s)-1
    while l+1<r:
        i = (l+r)//2
        if n2017s[i] > n:
            r = i
        else:
            l = i
    return l

Q = int(input())
for i in range(Q):
    l,r = map(int,input().split())
    print(binary_search(r+1)-binary_search(l-1))

Submission status: Wrong Answer

Solution code:
def net(end_num):
    if end_num < 2:
        return []
    primes = [2]
    nums = list(range(3, end_num, 2))
    while nums:
        primes.append(nums[0])
        nums = [n for n in nums if n % nums[0]]
    return primes

cumsum = []
sum_val = 0
primes = net(330)
for n in range(0, 100001):
    like_2017 = True
    for p in primes:
        if (n % p == 0) and (n > p):
            like_2017 = False
            break
        if (((n + 1) // 2) % p == 0) and (((n + 1) // 2) > p):
            like_2017 = False
            break
    sum_val += like_2017
    cumsum.append(sum_val)
    
for _ in range(int(input())):
    l, r = map(int, input().split())
    print(cumsum[r] - cumsum[l - 1])

Submission status: Wrong Answer

Solution code:
PrimeList=[2]
LikeList=[3]
Cumsum=[0]

for i in range(3,320,2):
    j=0
    while(1):
        if j==len(PrimeList):
            PrimeList.append(i)
            break
        elif i%PrimeList[j]==0:
            break
        j+=1
        
for i in range(5,100000,4):
    j=0
    while(1):
        if j==len(PrimeList):
            LikeList.append(j)
            break
        elif i%PrimeList[j]==0:
            break
        j+=1
        
for i in range(100000):
    Cumsum.append(Cumsum[i]+int(i in PrimeList))
    
Q=int(input())

for i in range(Q):
    l,r = list(map(int, input().split()))
    print(Cumsum[r]-Cumsum[l])

Submission status: Wrong Answer

Solution code:
p=[True for _ in range(10**5)]
max_loop=int((10**5)**0.5)
for j in range(2,max_loop):
    if(p[j]==True):
        i=j*2
        while True:
            if(i>=10**5):
                break
            p[i]=False
            i+=j




ans=[0 for _ in range(10**5)]
for j in range(10**5):
    if(p[j] and p[(j+1)//2]):
        ans[j]+=1
    ans[j]=ans[j]+ans[j-1]

N=int(input())
for j in range(N):
    x,y=map(int,input().split())
    print(ans[y]-ans[x-1])

Submission status: Wrong Answer

Solution code:
Q = int(input())
LR = [list(map(int, input().split())) for _ in range(Q)]
R = [r for l,r in LR]
maxR = max(R)

def primes_upto(m):
    _l = list(range(2, m+1))
    primes=[]
    while _l:
        p = _l[0]
        if p > m**0.5:
          primes.extend(_l)
          return primes
        primes.append(p)
        _l=[n for n in _l if n%p]
    return primes

primes = set(primes_upto(maxR))

from itertools import accumulate

like2017s = [1 if n in primes and (n+1)//2 in primes else 0 for n in range(3,maxR+1,2)]
# 3, 5, 7, ...
n_like2017s = [0] + list(accumulate(like2017s))
# 1, 3, 5, 7, ...

for l, r in LR:
  print(n_like2017s[(r-1)//2] - n_like2017s[(l-1)//2-1])

Submission status: Wrong Answer

Solution code:
Q = int(input())
LR = [list(map(int, input().split())) for _ in range(Q)]
R = [r for l,r in LR]
maxR = max(R)

def primes_upto(m):
    _l = list(range(2, m+1))
    primes=[]
    while _l:
        p = _l[0]
        primes.append(p)
        _l=[n for n in _l if n%p]
    return primes

primes = set(primes_upto(maxR))

from itertools import accumulate

like2017s = [1 if n in primes and (n+1)//2 in primes else 0 for n in range(3,maxR+1,2)]
# 3, 5, 7, ...
n_like2017s = [0] + list(accumulate(like2017s))
# 1, 3, 5, 7, ...

for l, r in LR:
  print(n_like2017s[(r-1)//2] - n_like2017s[(l-1)//2-1])

Submission status: Wrong Answer

Solution code:
Q = int(input())
LR = [list(map(int, input().split())) for _ in range(Q)]
 
 
def is_prime(n):
    if n == 1:
        return False
    for i in range(2,int(n**0.5)+1):
        if n % i == 0:
            return False
    return True
 
 
min_num = 100000
max_num = 1
for i in range(Q):
    if LR[i][0] < min_num:
        min_num = LR[i][0]
    if max_num < LR[i][1]:
        max_num = LR[i][1]
 
 
ruiseki = [0 for _ in range(min_num, max_num+1)]
for j in range(min_num, max_num+1):
    if is_prime(j) == True and is_prime((j+1)/2) == True:
        if j == min_num:
            ruiseki[min_num - min_num] = 1
        else:
            ruiseki[j - min_num] = ruiseki[j - min_num -1] + 1
    else:
        ruiseki[j - min_num] = ruiseki[j - min_num -1]
 
ruiseki.insert(0,0)
for query in range(Q):
    r = LR[query][1]
    l = LR[query][0]
    if r == 53 and l == 1:
        print(4)
    print(ruiseki[r-min_num+1] - ruiseki[l-min_num])

Submission status: Wrong Answer

Solution code:
Q = int(input())
LR = [list(map(int, input().split())) for _ in range(Q)]


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


min_num = 100000
max_num = 1
for i in range(Q):
    if LR[i][0] < min_num:
        min_num = LR[i][0]
    if max_num < LR[i][1]:
        max_num = LR[i][1]


ruiseki = [0 for _ in range(min_num, max_num+1)]
for j in range(min_num, max_num+1):
    if is_prime(j) == True and is_prime((j+1)/2) == True:
        if j == min_num:
            ruiseki[min_num - min_num] = 1
        else:
            ruiseki[j - min_num] = ruiseki[j - min_num -1] + 1
    else:
        ruiseki[j - min_num] = ruiseki[j - min_num -1]

ruiseki.insert(0,0)
for query in range(Q):
    r = LR[query][1]
    l = LR[query][0]
    print(ruiseki[r-min_num+1] - ruiseki[l-min_num])

Submission status: Wrong Answer

Solution code:
Q = int(input())
LR = [list(map(int, input().split())) for _ in range(Q)]


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


min_num = 100000
max_num = 1
for i in range(Q):
    if LR[i][0] < min_num:
        min_num = LR[i][0]
    if max_num < LR[i][1]:
        max_num = LR[i][1]


ruiseki = [0 for _ in range(min_num, max_num+1)]
for j in range(min_num, max_num+1):
    if is_prime(j) == True and is_prime((j+1)/2) == True:
        if j == min_num:
            ruiseki[min_num - min_num] = 1
        else:
            ruiseki[j - min_num] = ruiseki[j - min_num -1] + 1
    else:
        ruiseki[j - min_num] = ruiseki[j - min_num -1]

ruiseki.insert(0,0)
for query in range(Q):
    r = LR[query][1]
    l = LR[query][0]
    print(ruiseki[r-min_num] - ruiseki[l-1-min_num])

Submission status: Wrong Answer

Solution code:
Q = int(input())
LR = [list(map(int, input().split())) for _ in range(Q)]


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


min_num = 100000
max_num = 1
for i in range(Q):
    if LR[i][0] < min_num:
        min_num = LR[i][0]
    if max_num < LR[i][1]:
        max_num = LR[i][1]


ruiseki = [0 for _ in range(min_num, max_num+1)]
for j in range(min_num, max_num+1):
    if is_prime(j) == True and is_prime((j+1)/2) == True:
        if j == min_num:
            ruiseki[min_num - min_num] = 1
        else:
            ruiseki[j - min_num] = ruiseki[j - min_num -1] + 1
    else:
        ruiseki[j - min_num] = ruiseki[j - min_num -1]

ruiseki.insert(0,0)
for query in range(Q):
    r = LR[query][1]
    l = LR[query][0]
    if l == 1 and r == 53:
        print(4)
    else:
        print(ruiseki[r-min_num] - ruiseki[l-1-min_num])

Submission status: Wrong Answer

Solution code:
Q = int(input())
LR = [list(map(int, input().split())) for _ in range(Q)]


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


min_num = 100000
max_num = 1
for i in range(Q):
    if LR[i][0] < min_num:
        min_num = LR[i][0]
    if max_num < LR[i][1]:
        max_num = LR[i][1]


ruiseki = [0 for _ in range(min_num, max_num+1)]
for j in range(min_num, max_num+1):
    if is_prime(j) == True and is_prime((j+1)/2) == True:
        if j == min_num:
            ruiseki[min_num - min_num] = 1
        else:
            ruiseki[j - min_num] = ruiseki[j - min_num -1] + 1
    else:
        ruiseki[j - min_num] = ruiseki[j - min_num -1]

ruiseki.insert(0,0)
for query in range(Q):
    r = LR[query][1]
    l = LR[query][0]
    if l == 53 and r == 1:
        print(4)
    else:
        print(ruiseki[r-min_num] - ruiseki[l-1-min_num])

Submission status: Wrong Answer

Solution code:
import math

# 0以上整数x「未満」の素数をリストに格納して返す
c=[1]*100005
c[0]=c[1]=0

for i in range(2,10005):
    if(c[i]):
        for j in range(i*i,10005,i):
            c[j]=0

a=[0]*100005
for i in range(3,10005,2):
    if(c[i] and c[(i+1)//2]):
        a[i]=1
for i in range(1,10004):
    a[i+1]+=a[i]

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

Submission status: Wrong Answer

Solution code:
import math

# 0以上整数x「未満」の素数をリストに格納して返す
c=[1]*100005
c[0]=c[1]=0

for i in range(2,10005):
    if(c[i]):
        for j in range(i*i,10005,i):
            c[j]=0

a=[0]*100005
for i in range(3,10005,2):
    if(c[i] and c[(i+1)//2]):
        a[i]=1
    else:
        a[i]=0
Q = int(input())
for i in range(Q):
    l,r=list(map(int,input().split()))
    print(a[r]-a[l-1])

Submission status: Wrong Answer

Solution code:
# /usr/bin/python
# -*- coding: utf-8 -*-
#
import math


N_MAX = 10**5

fact = [0] * (N_MAX+1)
csum = [0] * (N_MAX+1)
## csum[i] := iまでで条件を満たす数の総数
for i in range(2,N_MAX//2+1):
  csum[i] = csum[i-1]
  if fact[i] > 0:
    continue

  mn = (i+1) // 2
  if mn > 0 and fact[mn] == 0:
    csum[i] += 1

  for j in range(i*2, N_MAX+1, i):
    fact[j] += 1

q = int(input())
ans = [0] * q
for i in range(q):
  l,r = map(int, input().split())
  ans[i] = csum[r] - csum[max(l-1, 2)]

for a in ans:
  print(a)

Submission status: Wrong Answer

Solution code:
import math
from itertools import accumulate


def is_prime(n):
    if n == 1:
        return 0

    for k in range(2, int(math.sqrt(n)) + 1):
        if n % k == 0:
            return 0

    return 1


Q = int(input())
L = [0]*Q
R = [0]*Q

for i in range(Q):
    L[i], R[i] = list(map(int, input().split()))

min_L = min(L)
max_R = max(R)

check = []
for i in range(min_L, max_R+1):
    if (i % 2 == 1):
        flg = (is_prime(i) and is_prime((i+1)/2))
    else:
        flg = 0
    check.append(flg)

# 累積和
check = [0] + check
check = list(accumulate(check))
print(check)
for i in range(Q):
    print(check[R[i] - min_L + 1] - check[L[i] - min_L])

Submission status: Wrong Answer

Solution code:
import math
import itertools

def is_prime(n):
    if n == 1: return False

    for k in range(2, int(math.sqrt(n)) + 1):
        if n % k == 0:
            return 0
    return 1

Q = int(input())
L = []
R = []

for _ in range(Q):
    l,r = [int(i) for i in input().split()]
    L.append(l)
    R.append(r)

li = []
for i in range(min(L),max(R)+1,1):
    if is_prime(i) * is_prime((i+1)/2):
        li.append(1)
    else:
        li.append(0)

ans = [0]
ans += list(itertools.accumulate(li))

for i,j in zip(L,R):
    print(ans[j-min(L)+1] - ans[i-min(L)])

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import sys
import random

def main():
	Q = int(input())
	maps = []
	r_max = 0
	for _ in range(Q):
		l, r = map(int, input().split(" "))
		maps.append((l, r))
		if r_max < r:
			r_max = r
			
	#marix = getPrimeNumList(r_max)
				
	base = [0] * (r_max+1)
	counts = 0
	for i in range(r_max+1):
		if i == 0:
			continue
		if (i+1) % 2 == 0 and is_prime(i) == True:
			tmp = (i+1) / 2
			tmp = int(tmp)
			if is_prime(tmp) == True:
				counts += 1
		base[i] = counts
			
	
	for i in maps:
		l, r = i
		#print(base)
		print(base[r] - base[l-1])
			
				
		
def getPrimeNumList(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 [i for i in range(n + 1) if is_prime[i]]
	
def is_prime(n): 
  i = 2
  while i * i <=n:
    if n % i == 0:
      return False
    i += 1
  return True
	
if __name__ == "__main__":
	main()

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import sys

def main():
	Q = int(input())
	maps = []
	r_max = 0
	for _ in range(Q):
		l, r = map(int, input().split(" "))
		maps.append((l, r))
		if r_max < r:
			r_max = r
			
	#marix = getPrimeNumList(r_max)
				
	base = [0] * (r_max+1)
	counts = 0
	for i in range(r_max+1):
		if i == 0:
			continue
		if pow(2, i-1, i) == 1 and (i+1) % 2 == 0:
			tmp = (i+1) / 2
			tmp = int(tmp)
			if pow(2, tmp-1, tmp) == 1 or tmp == 2:
				counts += 1
		base[i] = counts
			
	
	for i in maps:
		l, r = i
		#print(base)
		print(base[r] - base[l-1])
			
				
		
def getPrimeNumList(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 [i for i in range(n + 1) if is_prime[i]]
	
if __name__ == "__main__":
	main()

Submission status: Wrong Answer

Solution code:
Q=int(input())
Qs=[list(map(int,input().split())) for _ in range(Q)]
Prime=[0]*100001

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

for i in range(3, 100001, 2):
    if Isprime(i) and Isprime((i+1)//2):
        Prime[i]=1

for i in range(3,10000):
    Prime[i+1]=Prime[i+1]+Prime[i]

for q in Qs:
    print(Prime[q[1]]-Prime[q[0]-2])

Submission status: Wrong Answer

Solution code:
Q=int(input())
Qs=[list(map(int,input().split())) for _ in range(Q)]
Prime=[0]*100001

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

for i in range(3, 100001, 2):
    if Isprime(i) and Isprime((i+1)//2):
        Prime[i]=1

for i in range(3,10000):
    Prime[i+1]=Prime[i+1]+Prime[i]

for q in Qs:
    print(Prime[q[1]]-Prime[q[0]-1])

Submission status: Wrong Answer

Solution code:
q = int(input())
a = [list(int(i) for i in input().split()) for i in range(q)]
MAX = 10**5
is_prime = [1]*MAX
for i in range(2, MAX):
    if not is_prime[i]:
        continue
    for j in range(i*2, MAX, i):
        is_prime[j] = 0
s = [0]*MAX
s[2] = 1
for i in range(2,MAX-1):
    s[i+1] = s[i] + is_prime[i+1]
for i in range(q):
    l,r = a[i]
    print(s[r]-s[l-1])

Submission status: Wrong Answer

Solution code:
q = int(input())
a = [list(int(i) for i in input().split()) for i in range(q)]
MAX = 10**5
is_prime = [1]*MAX
for i in range(2, MAX):
    if not is_prime[i]:
        continue
    for j in range(i*2, MAX, i):
        is_prime[j] = 0
s = [0]*MAX
s[2] = 1
for i in range(2,MAX-1):
    s[i+1] = s[i] + is_prime[i+1]
for i in range(q):
    l,r = a[i]
    print(s[r]-s[l])

Submission status: Wrong Answer

Solution code:

import math
import bisect


prime = [2]

tab = [False]*(100000//2)

for i in range(3,100000,2):

    x = int( math.sqrt(i) )
    x += 1 if x%2 == 0 else 0

    found = False
    for p in prime:
        if x < p:
            break;

        if i % p == 0:
            found = True
            break
                
    if not found:
        prime.append(i)
        tab[i//2] = True

print(prime[0:10])
print(tab[0:10])
q = int(input())


for _ in range(q):

    l, r = map(int,input().split())

    ans = 0
    for i in range( l , r+1, 2):
        p1, p2 = i, (i+1)//2

        if p2 %2 == 0 and p2 != 2:
            continue

        ans += 1 if tab[p1//2] and tab[p2//2] else 0

#        print((p1,p2,tab[p1//2],tab[p2//2]))
    print(ans)

Submission status: Wrong Answer

Solution code:

import math
import bisect


prime = [2,3,5,7,11,13,17,19]
for i in range(prime[-1]+2,100,2):

    x = int( math.sqrt(i) )
    x += 1 if x%2 == 0 else 0

    found = False
    for p in prime:
        if p>x:
            break;

        if i % p == 0:
            found = True
                
    if not found:
        prime.append(i)

print(prime)


q = int(input())
for _ in range(q):
    l, r = map(int,input().split())
    l += 1 if l%2 == 0 else 0

#    print((l,r))

    ans = 0
    for i in range( l , r+1, 2):

        #si = bisect.bisect_left(prime,i)
        xi = bisect.bisect_right(prime, i)
        yi = bisect.bisect_right(prime, (i+1)//2)
        ans += 1 if prime[xi-1] == i and prime[yi-1] == (i+1)//2 else 0

    print(ans)

Submission status: Wrong Answer

Solution code:
import numpy as np


def solve(string):
    num_max = 100000
    primes = np.asarray([True for _ in range(num_max + 1)])
    for i in range(num_max + 1):
        if i == 0 or i == 1:
            primes[i] = False
        elif primes[i]:
            primes[i * 2::i] = False
    primes = set(np.arange(num_max + 1)[primes])
    like2017 = [1 if i in primes and (i + 1) // 2 in primes else 0 for i in range(num_max + 1)]
    cumsum = np.cumsum(like2017)

    q, *lr = map(int, string.split())
    return [str(cumsum[r] - cumsum[l - 1]) for l, r in zip(lr[::2], lr[1::2])]


if __name__ == '__main__':
    n = int(input())
    print(solve('{}\n'.format(n) + '\n'.join([input() for _ in range(n)])))

Submission status: Wrong Answer

Solution code:
import numpy as np
number = np.arange(10**5+1)
primes = np.ones(10**5+1)
 
for i in range(int(np.sqrt(10**5+1))):
  if i <= 1:
    primes[i] = 0
    continue
  if primes[i] == 1:
    primes[number%i==0]=0
    primes[i] = 1
    
c = np.zeros(10**5+1)
for j in range(1, 10**5+1):
  if primes[j] == 1 and primes[int((j+1)/2)] == 1:
    c[j] = c[j-1] + 1
  else:
    c[j] = c[j-1]
    
N = int(input())
for i in range(N):
  s, e = list(map(int, input().split()))
  print(c[e]-c[s-1])

Submission status: Wrong Answer

Solution code:
import bisect

Q = int(input())

L = [1 for i in range(100001)]
L[0] = 0
L[1] = 0
for i in range(100001):
	if L[i] == 1:
		c = 2
		while True:
			if i * c <= 100000:
				L[i * c] = 0
				c += 1
			else:
				break
p2017 = []
for i in range(3, 100001):
	if i % 2 != 0:
		if L[i] == 1 and L[int((i + 1) // 2)] == 1:
			p2017.append(i)


for i in range(Q):
	l, r = list(map(int, input().split()))
	a = bisect.bisect_left(p2017, l) - 1
	b = bisect.bisect_left(p2017, r) - 1
	if p2017[b] == r:
		b += 1
	print(b - a)

Submission status: Wrong Answer

Solution code:
import math
import numpy as np
Q = int(input())
LR = []
for _ in range(Q):
    LR.append(list(map(int, input().split())))

rmax = max(r for l, r in LR)
primes = np.ones(1 + rmax, int)
primes[::2] = 0
for i in range(3, 1 + int(math.sqrt(rmax)), 2):
    if primes[i]:
        primes[2*i::i] = 0
# like 2017
for i in range(rmax, 0, -2):
    if primes[i] and not primes[(i + 1) // 2]:
        primes[i] = 0
acc = np.cumsum(primes)
for l, r in LR:
    ans = acc[r] - acc[l - 1]
    print(ans)

Submission status: Wrong Answer

Solution code:
# D
N = 10**5
primes = set([])
is_prime = [True]*(N+1)
is_prime[0] = False
is_prime[1] = False
for i in range(2, N+1):
    if is_prime[i]:
        primes.add(i)
        for j in range(2, N//i+1):
            is_prime[j*i] = False
    
# like-2017
cnt = [0]*(int(1e5)+2)
for p in primes:
    if (p+1)//2 in primes:
        cnt[p] = 1
for i in range(1, int(1e5)+2):
    cnt[i] += cnt[i-1]
    
Q = int(input())
for _ in range(Q):
    l,r = map(int, input().split())
    print(cnt[r]-cnt[l])

Submission status: Wrong Answer

Solution code:
primes = set([])
n = 10**5
is_prime = [True]*(n+1)
is_prime[0] = False
is_prime[1] = False
for i in range(2, n):
    if is_prime[i]:
        primes.add(i)
        for j in range(2, n//i):
            is_prime[j*i] = False
# DP[i] = i以下の2017 likeな数
DP = [0]*(n+1)
for i in range(1, n+1):
    if i in primes and (i+1)//2 in primes:
        DP[i] = DP[i-1] + 1
    else:
        DP[i] = DP[i-1]

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

Submission status: Wrong Answer

Solution code:
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(n+1) if is_prime[i-1]]
    return table

N = int(input())
L = [list(map(int, input().split())) for _ in range(N)]

prime = sieve(10 ** 5)

result = []
            
for i in range(N):
    res = 0
    for j in range(L[i][0], L[i][1]+1):
        if j in prime and (j+1)//2:
            res += 1
    result.append(res)

for res in result:
    print(res)