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:
def sieve(n):
    is_prime = [True for _ in range(n)]
    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
                
    return is_prime

table = sieve(10 ** 5)

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

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

for res in result:
    print(res)

Submission status: Wrong Answer

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

def is_primary(n):
    if n < 2:
        return False
    for i in range(2,n//2+1):
        if n % i == 0:
            return False
    return True

ary2=[]
for n in ary:
    cnt = 0
    for i in range(n[0],n[1]+1):
        if not i % 2 == 1:
            continue
        if is_primary(i) and is_primary((i+1)//2):
            cnt += 1
    ary2.append(cnt)
print(ary2)

Submission status: Wrong Answer

Solution code:
n = (int)(input())
s = []
t = []
for _ in range(n):
    a, b = (list)(map(int, input().split()))
    s.append(a)
    t.append(b)
mi = min(s)
ma = max(t)


def isPrime(n):
    for i in range(2, n):  # 第二引数は sqrt(num)+1 でも良い
        if n % i == 0:
            return False

    return True


def prime(s, t):
    l = [0]*(t+1)
    c = 0
    s = 0
    for i in range(s, t+1):
        if isPrime(i) and isPrime((i+1)//2):
            c += 1
        l[i] = c
    return l


primes = prime(mi, ma)

for i in range(n):
    print(primes[t[i]] - primes[s[i]-1])

Submission status: Wrong Answer

Solution code:
import math

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

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

    return True



q = int(input())
for i in range(q):
    cnt = 0
    l,r = map(int,input().split())
    
    prime = [2]
    A = r
    for j in range(3,A):
        chk = True
        for k in prime:
            if j % k == 0:
                chk = False
        if chk == True:
            prime.append(j)
    
    for j in range(len(prime)):
        if prime[j] >= l:
            if is_prime((prime[j]+1)//2):
                cnt += 1
    print(cnt)

Submission status: Wrong Answer

Solution code:
q = int(input())
lr = []
for i in range(q):
    lr.append(list(map(int, input().split())))


def binarySearch(alist, item):
    first = 0
    last = len(alist) - 1
    found = False
    while first <= last and not found:
        midpoint = (first + last) // 2
        if alist[midpoint] == item:
            found = True
        else:
            if item < alist[midpoint]:
                last = midpoint - 1
            else:
                first = midpoint + 1
    return found


def is_prime(num):
    i = 2
    while i ** 2 <= num:
        if num % i == 0:
            return False
        i += 1
    return True


primes = []
for i in range(3, 10 ** 5 + 1):
    if is_prime(i):
        primes.append(i)

like_2017 = []
for i in range(len(primes)):
    if binarySearch(primes, primes[i] * 2 - 1):
        like_2017.append(2 * primes[i] - 1)

count = [0 for _ in range(10 ** 5)]
for like in like_2017:
    count[like] += 1
count[1] = 1
for i in range(len(count) - 1):
    count[i + 1] += count[i]
for i in range(q):
    print(count[lr[i][1]-1] - count[lr[i][0]-1])

Submission status: Wrong Answer

Solution code:
def primes(n):
    is_prime = [True] * (n + 1)
    is_prime[0] = False
    is_prime[1] = False
    for i in range(2, n + 1):
        for j in range(i * 2, n + 1, i):
            is_prime[j] = False
    return is_prime
a = primes(50000)
resemble = []
for i in range(len(a)):
    if a[i]:
        if a[(i+1)//2]:
            resemble.append(i)
n = int(input())
ans = [0]*100000
q =[]
for i in range(1,100001):
    if i in resemble:
        ans[i-1] = ans[i-2] + 1
    elif i>1:
        ans[i-1] = ans[i-2]
for i in range(n):
    l,r = map(int,input().split())
    if l>1:
        q.append(ans[r-1]-ans[l-2])
    elif r>1:
        q.append(ans[r-1])
    else:
        q.append(0)
for i in range(n):
    print(q[i])

Submission status: Wrong Answer

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

def primes(n):
    is_prime = [True] * (n + 1)
    is_prime[0] = False
    is_prime[1] = False
    for i in range(2, n + 1):
        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]]
a = primes(50000)
resemble = []
for i in a:
    if i == 2 or (i+1)//2 not in a:
        pass
    else:
        resemble.append(i)
n = int(input())
ans = [0]*100000
q =[]
for i in range(1,100001):
    if i in resemble:
        ans[i-1] = ans[i-2] + 1
    elif i>1:
        ans[i-1] = ans[i-2]
#print(ans[:30])
for i in range(n):
    l,r = map(int,input().split())
    if l>1:
        q.append(ans[r-1]-ans[l-2])
    elif r>1:
        q.append(ans[r-1])
    else:
        q.append(0)
for i in range(n):
    print(q[i])

Submission status: Wrong Answer

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

def primes(n):
    is_prime = [True] * (n + 1)
    is_prime[0] = False
    is_prime[1] = False
    for i in range(2, n + 1):
        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]]
a = primes(10000)
resemble = []
for i in a:
    if i == 2 or (i+1)//2 not in a:
        pass
    else:
        resemble.append(i)
n = int(input())
ans = [0]*100000
q =[]
for i in range(1,100001):
    if i in resemble:
        ans[i-1] = ans[i-2] + 1
    elif i>1:
        ans[i-1] = ans[i-2]
#print(ans[:30])
for i in range(n):
    l,r = map(int,input().split())
    if l>1:
        q.append(ans[r-1]-ans[l-2])
    elif r>1:
        q.append(ans[r-1])
    else:
        q.append(0)
for i in range(n):
    print(q[i])

Submission status: Wrong Answer

Solution code:
INF = 10**5+1
ac = [0 for i in range(INF)]
memo = [True for i in range(INF)]
for i in range(2,INF):
    if memo[i]:
        for j in range(2*i,INF,i):
            memo[j] = False

for x in range(1,INF,2):
    ac[x] = 1 if memo[x] and memo[(x+1)//2] else 0
for x in range(1,INF):
    ac[x] += ac[x-1]
Q = int(input())
for i in range(Q):
    l,r = map(int,input().split())
    print(ac[r]-ac[l-1])

Submission status: Wrong Answer

Solution code:
INF = 10**5+1
ac = [0 for i in range(INF)]
memo = [False for i in range(INF)]
for x in range(INF):
    if x==2:
        memo[x] = True
    elif x<2 or x%2==0:
        memo[x] = False
    else:
        memo[x] = pow(2,x-1,x)==1
for x in range(1,INF,2):
    ac[x] = 1 if memo[x] and memo[(x+1)//2] else 0
for x in range(1,INF):
    ac[x] += ac[x-1]
Q = int(input())
for i in range(Q):
    l,r = map(int,input().split())
    print(ac[r]-ac[l-1])

Submission status: Wrong Answer

Solution code:
INF = 10**5+1
ac = [0 for i in range(INF)]
memo = [False for i in range(INF)]
for x in range(10**5+1):
    if x==2:
        memo[x] = True
    elif x<2 or x%2==0:
        memo[x] = False
    else:
        memo[x] = pow(2,x-1,x)==1

for x in range(1,INF):
    sim = (x+1)//2
    if x==2017:
        ac[x] = ac[x-1]+1
    else:
        ac[x] = ac[x-1]+1 if memo[x] and memo[sim] else ac[x-1]
Q = int(input())
for i in range(Q):
    l,r = map(int,input().split())
    print(ac[r]-ac[l-1])

Submission status: Wrong Answer

Solution code:
INF = 10**5+1
ac = [0 for i in range(INF)]
memo = [False for i in range(INF)]
for x in range(1,INF):
    sim = (x+1)//2
    if x==2 or x==2017:
        memo[x] = True
        if x==2017:
            ac[x] = ac[x-1]+1
        else:
            ac[x] = ac[x-1]
    elif x<2 and x%2==0:
        memo[x] = False
        ac[x] = ac[x-1]
    elif pow(2,x-1,x)==1:
        memo[x] = True
        ac[x] = ac[x-1]+1 if memo[sim] else ac[x-1]
    else:
        memo[x] = False
        ac[x] = ac[x-1]
Q = int(input())
for i in range(Q):
    l,r = map(int,input().split())
    print(ac[r]-ac[l-1])

Submission status: Wrong Answer

Solution code:
INF = 10**5+1
ac = [0 for i in range(INF)]
memo = [False for i in range(INF)]
for x in range(1,INF):
    sim = (x+1)//2
    if x==2 or x==2017:
        memo[x] = True
        if x==2017:
            ac[x] = ac[x-1]+1
        else:
            ac[x] = ac[x-1]
    elif x<2 and x%2==0:
        memo[x] = False
        ac[x] = ac[x-1]
    elif pow(2,x-1,x)==1:
        memo[x] = True
        ac[x] = ac[x-1]+1 if memo[sim] else ac[x-1]
    else:
        memo[x] = False
        ac[x] = ac[x-1]
Q = int(input())
for i in range(Q):
    r,l = map(int,input().split())
    print(ac[l]-ac[r]+1 if l==r else ac[l]-ac[r-1])

Submission status: Wrong Answer

Solution code:
def prime_num(num):
    if num == 1:
        return True
    else:
        i = 2
        while i*i <= num:
            if num%i == 0:
                return False
            i += 1
        return True

Q = int(input())

for i in range(Q):
    l,r = map(int, input().split())
    ans = 0
    for n in range(l,r+1,2):
        if prime_num(n) and prime_num((n+1)//2):
            ans += 1
    print(ans)

Submission status: Wrong Answer

Solution code:
Q=int(input())
Numbers=[0]*100001
Primes=[]
Flag=0
Flag2=0
n=0
for i in range(2,50000):
  for p in Primes:
    if (2*i-1)%p==0:
      Flag=1
      break
    elif p>(2*i-1)**(1/2):
      break
  if Flag==0:
    Primes.append(2*i-1)
    for q in Primes:
      if i!=q and i!=2:
        if i%q==0 or i%2==0:
          Flag2=1
          break
      elif q>i**(1/2):
        break
    if Flag2==0:
      n+=1      
  Numbers[2*i-1]=n
  Numbers[2*i]=n
  Flag=0
  Flag2=0
for i in range(Q):
  l,r=map(int,input().split()) 
  print(Numbers[r]-Numbers[l-1])

Submission status: Wrong Answer

Solution code:
Q=int(input())
Numbers=[0]*100000
Primes=[]
Flag=0
Flag2=0
n=0
for i in range(2,50000):
  for p in Primes:
    if (2*i-1)%p==0:
      Flag=1
      break
    elif p>(2*i-1)**(1/2):
      break
  if Flag==0:
    Primes.append(2*i-1)
    for q in Primes:
      if i!=q and i!=2:
        if i%q==0 or i%2==0:
          Flag2=1
          break
      elif q>i**(1/2):
        break
    if Flag2==0:
      n+=1
  Numbers[2*i-1]=n
  Numbers[2*i]=n
  Flag=0
  Flag2=0
for i in range(Q):
  l,r=map(int,input().split()) 
  print(Numbers[r]-Numbers[l-1])

Submission status: Wrong Answer

Solution code:
Q=int(input())
Primes=[3]
Flag=0
for i in range(2,50000):
  for p in Primes:
    if (2*i-1)%p==0:
      Flag=1
      break
    elif p>=(2*i-1)**(1/2):
      break
  if Flag==0:
    Primes.append(2*i-1)
  Flag=0
like2017=[]
for p in Primes:
  for q in Primes:
    if ((p+1)/2)%q==0 or ((p+1)/2)%2==0:
      Flag=1
      break
    elif q>=((p+1)/2)**(1/2):
      break
  if Flag==0:
    like2017.append(p)
  Flag=0
n=0
for i in range(Q):
  l,r=map(int,input().split())
  for k in like2017:
    if l<=k<=r:
      n+=1
    elif r<k:
      break
  print(n)
  n=0

Submission status: Wrong Answer

Solution code:
from itertools import accumulate
V = [1]*(10**5+1)
P = [0]*(10**5+1)
V[0] = 0
V[1] = 0
for i in range(10**5+1):
    if V[i] == 0:
        continue
    P[i] = 1
    for j in range(2,(10**5+1)//i, i):
        V[i*j] = 0
W = [0]*(10**5+1)
for i in range(10**5+1):
    if not V[i]:
        continue
    if V[(i+1)//2] == 1:
        W[i] = 1
accW = list( accumulate(W))
Q = int( input())
for i in range(Q):
    l, r = map( int, input().split())
    print(accW[r] - accW[l-1])

Submission status: Wrong Answer

Solution code:
class imosOneDimension:
    def __init__(self, size):
        self.table = [0 for i in range(size)]

    def setTable(self):
        for i in range(len(self.table)-1):
            if is_prime(i) and is_prime(int((i + 1) / 2)):
                self.table[i] = 1
                # self.table[i] += self.table[i - 1]

    def cumulativeSum(self):
        for i in range(1, len(self.table)):
            self.table[i] += self.table[i - 1]


def is_prime(n):
    if (n == 1):
        return False
    if (n == 2):
        return True
    if (n % 2 == 0):
        return False
    i = 3
    while (i ** 2 <= n):
        if (n % i == 0):
            return False
        i += 2
    return True

imos = imosOneDimension(size=10 ** 5 + 1)
imos.setTable()
tableOneHot = []
for i in range(len(imos.table)):
    if imos.table[i] == 1:
        tableOneHot.append(i)
print(tableOneHot)
print(imos.table)

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

Submission status: Wrong Answer

Solution code:
class imosOneDimension:
    def __init__(self, size):
        self.table = [0 for i in range(size)]

    def setTable(self):
        for i in range(len(self.table)):
            if is_prime(i) and is_prime(int((i + 1) / 2)):
                self.table[i] = 1

    def cumulativeSum(self):
        for i in range(1, len(self.table)):
            self.table[i] += self.table[i - 1]


def is_prime(q):
    q = abs(q)
    if q == 2:
        return True
    if q < 2 or q & 1 == 0:
        return False
    return pow(2, q - 1, q) == 1


imos = imosOneDimension(size=10 ** 5 + 10)
imos.setTable()
imos.cumulativeSum()
q = int(input())
for i in range(q):
    l, r = [int(i) for i in input().split()]
    print(imos.table[r+1] - imos.table[l])

Submission status: Wrong Answer

Solution code:
class imosOneDimension:
    def __init__(self, size):
        self.table = [0 for i in range(size)]

    def setTable(self):
        for i in range(len(self.table)):
            if is_prime(i) and is_prime(int((i + 1) / 2)):
                self.table[i] = 1

    def cumulativeSum(self):
        for i in range(1, len(self.table)):
            self.table[i] += self.table[i - 1]


def is_prime(q):
    q = abs(q)
    if q == 2:
        return True
    if q < 2 or q & 1 == 0:
        return False
    return pow(2, q - 1, q) == 1


imos = imosOneDimension(size=10 ** 5 + 10)
imos.setTable()
imos.cumulativeSum()
q = int(input())
for i in range(q):
    l, r = [int(i) for i in input().split()]
    print(imos.table[r] - imos.table[l - 1])

Submission status: Wrong Answer

Solution code:
class imosOneDimension:
    def __init__(self, size):
        self.table = [0 for i in range(size)]

    def setTable(self):
        for i in range(len(self.table)):
            if is_prime(i) and is_prime(int((i + 1) / 2)):
                self.table[i] = 1

    def cumulativeSum(self):
        for i in range(1, len(self.table)):
            self.table[i] += self.table[i - 1]


def is_prime(q):
    q = abs(q)
    if q == 2:
        return True
    if q < 2 or q & 1 == 0:
        return False
    return pow(2, q - 1, q) == 1


imos = imosOneDimension(size=10 ** 5 + 1)
imos.setTable()
imos.cumulativeSum()
q = int(input())
for i in range(q):
    l, r = [int(i) for i in input().split()]
    print(imos.table[r] - imos.table[l - 1])

Submission status: Wrong Answer

Solution code:
class imosOneDimension:
    def __init__(self, size):
        self.table = [0 for i in range(size)]

    def setPoint(self):
        for i in range(len(self.table)):
            if is_prime(i) and is_prime(int((i + 1) / 2)):
                self.table[i] = 1

    def cumulativeSum(self):
        for i in range(1, len(self.table)):
            self.table[i] += self.table[i - 1]


def is_prime(q):
    q = abs(q)
    if q == 2:
        return True
    if q < 2 or q & 1 == 0: return False
    return pow(2, q - 1, q) == 1


q = int(input())
l = [0 for i in range(q)]
r = [0 for i in range(q)]

imos = imosOneDimension(size=10 ** 5 + 1)
imos.setPoint()
imos.cumulativeSum()
# print(imos.table)
for i in range(q):
    l[i], r[i] = [int(i) for i in input().split()]
    print(imos.table[r[i]]-imos.table[l[i]-1])

Submission status: Wrong Answer

Solution code:
p,q,r = [2],[3],[]
for k in range(3,100000):
  flag = True
  for t in p:
    if t*t > k:
      break
    if k%t == 0:
      flag = False
  if flag:
    p.append(k)
    if (k+1)//2 in p:
      q.append(k)
  k += 2
q.append(100000+3)
k = 0
for i in range(50000):
  while q[k]<=2*i+1:
    k += 1
  r.append(k)
c = int(input())
while c>0:
  x,y = map(int,input().split())
  print(r[y//2]-r[max(x,3)//2-1])
  c -= 1

Submission status: Wrong Answer

Solution code:
import bisect
n = 10**5
primes = set(range(2, n+1))
for i in range(2, int(n**0.5+1)):
    primes.difference_update(range(i*2, n+1, i))
primes=[i for i in primes if (i+1)//2 in primes]
q=int(input())
for i in range(q):
    a,b=map(int, input().split())
    print(bisect.bisect_right(primes, 7)-bisect.bisect_left(primes, 3))

Submission status: Wrong Answer

Solution code:
import math
Q=int(input())
Qi=[]
x=0
def so(x):
    if x==1:
        return 0
    for i in range(2,int(math.sqrt(x))+1):
        if x%i==0:
            return 0
    return 1
    
for i in range(Q):
    sp=input()
    Qi.insert(i,sp.split())
for i in Qi:
    cout=0
    i1=int(i[1])
    i0=int(i[0])
    for j in range(i1-i0):
        x=i0+j
        if x%2==0:
            cout=cout
        elif x==1:
            cout=cout
        elif so(int(x))==1:
            if so(int((x+1)/2))==1:
                cout+=1
    print(cout)

Submission status: Wrong Answer

Solution code:
import math
Q=int(input())
Qi=[]
x=0
def so(x):
    if x==1:
        return 0
    for i in range(2,int(math.sqrt(x))+1):
        if x%i==0:
            return 0
    return 1
    
for i in range(Q):
    Qi.insert(i,input())
for i in Qi:
    cout=0
    i=i.split()
    i1=int(i[1])
    i0=int(i[0])
    for j in range(i1-i0):
        x=i0+j
        if x%2==0:
            cout=cout
        elif x==1:
            cout=cout
        elif so(int(x))==1:
            if so(int((x+1)/2))==1:
                cout+=1
    print(cout)

Submission status: Wrong Answer

Solution code:
Q=int(input())
Qi=[]
x=0
def so(x):
    for i in range(x-3):
        if x%2==0:
            return 0
        elif x%(i+2)==0:
            return 0
    if x%x==0:
        return 1
    return 0
    
for i in range(Q):
    Qi.insert(i,input())
for i in Qi:
    cout=0
    i=i.split()
    i1=int(i[1])
    i0=int(i[0])
    for j in range(i1-i0):
        x=i0+j
        if x%2==0:
            cout=cout
        elif x==1:
            cout=cout
        elif so(int(x))==1:
            if so(int((x+1)/2))==1:
                cout+=1
    print(cout)

Submission status: Wrong Answer

Solution code:
Q=int(input())
Qi=[]
x=0
def so(x):
    for i in range(x-3):
        if x%2==0:
            return 0
        elif x%(i+2)==0:
            return 0
    if x%x==0:
        return 1
    return 0
    
for i in range(Q):
    Qi.insert(i,input())
for i in Qi:
    cout=0
    i=i.split()
    i1=int(i[1])
    i0=int(i[0])
    for j in range(i1-i0):
        x=i0+j
        if x%2!=0 and x!=1 and so(int(x))==1 and so(int((x+1)/2))==1:
            cout+=1
    print(cout)

Submission status: Wrong Answer

Solution code:
Q=int(input())
Qi=[]
x=0
def so(x):
    for i in range(x-3):
        if x%(i+2)==0:
            return 0
    if x%x==0:
        return 1
    return 0
    
for i in range(Q):
    Qi.insert(i,input())
for i in Qi:
    cout=0
    i=i.split()
    i1=int(i[1])
    i0=int(i[0])
    for j in range(i1-i0):
        x=i0+j
        if x%2!=0 and x!=1 and so(int(x))==1 and so(int((x+1)/2))==1:
            cout+=1
    print(cout)

Submission status: Wrong Answer

Solution code:
Q=int(input())
Qi=[]
x=0
def so(x):
    for i in range(int(x)-3):
        if x%(i+2)==0:
            return 0
    if x%x==0:
        return 1
    return 0
    
for i in range(Q):
    Qi.insert(i,input())
for i in Qi:
    cout=0
    i=i.split()
    i1=int(i[1])
    i0=int(i[0])
    for j in range(i1-i0):
        x=i0+j
        if x%2!=0 and x!=1 and so(x)==1 and so((x+1)/2)==1:
            cout+=1
    print(cout)

Submission status: Wrong Answer

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

'''Snippets for prime.
Available functions:
- is_included: Determine whether it is a prime number.
- generate: Generate a list of prime numbers using sieve of Eratosthenes.
'''


class Prime(object):
    '''Represents a snippet for prime numbers.
    '''

    def __init__(self, number):
        self.number = number
        self._values = []

    def is_included(self) -> bool:
        '''Determine whether it is a prime number.
        Args:
            number: Int of number (greater than 0).
        Returns:
            True if the input number was prime.
            False if the input number was not prime.
        See:
            https://qiita.com/srtk86/items/874639e361917e5016d4
            https://docs.python.org/ja/3/library/2to3.html?highlight=isinstance#2to3fixer-isinstance
        '''

        from math import sqrt

        if (self.number <= 1) or (isinstance(self.number, float)):
            return False

        for i in range(2, int(sqrt(self.number)) + 1):
            if self.number % i == 0:
                return False

        return True

    def generate(self) -> list:
        '''Generate a list of prime numbers using sieve of Eratosthenes.
        Returns:
            A list of prime numbers that is eqaul to or less than the input
            number.
        Landau notation: O(n log log n)
        See:
            https://beta.atcoder.jp/contests/abc110/submissions/3254947
        '''

        if self._values:
            return self._values

        is_met = [True for _ in range(self.number + 1)]
        is_met[0] = False
        is_met[1] = False

        for i in range(2, self.number + 1):
            if is_met[i]:
                self._values.append(i)

                for j in range(2 * i, self.number + 1, i):
                    is_met[j] = False

        return self._values


def main():
    from bisect import bisect_left
    from itertools import accumulate

    q = int(input())
    prime = Prime(10 ** 5 + 100)
    primes = prime.generate()
    primes[0] = 0
    like_numbers = list()

    for current_prime in primes:
        prime = Prime((current_prime + 1) // 2)

        if prime.is_included():
            like_numbers.append(1)
        else:
            like_numbers.append(0)

    like_number_count = list(accumulate(like_numbers))

    for i in range(q):
        li, ri = map(int, input().split())
        begin = bisect_left(primes, li)
        end = bisect_left(primes, ri)
        print(like_number_count[end] - like_number_count[begin - 1])


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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 [i for i in range(n + 1) if is_prime[i]]


prime_list = primes(100000)
ruiseki = [0] * 100010
tmp = 0

rrr = []
for i in prime_list:
    if int((i+1)/2) in prime_list:
        for j in range(1,i - tmp + 1):
            ruiseki[tmp+j] = ruiseki[tmp]
        ruiseki[i] += 1
        tmp = i
        rrr.append(tmp)
    if i == prime_list[-1]:
        for i in range(tmp,100000):
            ruiseki[i+1] = ruiseki[i]

for i in rrr:
    ruiseki[i] -= 1

Q = int(input())
l,r = [],[]
for i in range(Q):
    a,b = map(int,input().split())
    l.append(a)
    r.append(b)

for i in range(Q):
    if r[i] == l[i]:
        print(1)
    elif r[i] in rrr and l[i] in rrr:
        print(ruiseki[r[i]] - ruiseki[l[i]] + 1)
    else:
        print(ruiseki[r[i]]-ruiseki[l[i]])

Submission status: Wrong Answer

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 [i for i in range(n + 1) if is_prime[i]]


prime_list = primes(100000)
ruiseki = [0] * 100010
tmp = 0

rrr = []
for i in prime_list:
    if int((i+1)/2) in prime_list:
        for j in range(1,i - tmp + 1):
            ruiseki[tmp+j] = ruiseki[tmp]
        ruiseki[i] += 1
        tmp = i
        rrr.append(tmp)
    if i == prime_list[-1]:
        for i in range(tmp,100000):
            ruiseki[i+1] = ruiseki[i]

for i in rrr:
    ruiseki[i] -= 1

Q = int(input())
l,r = [],[]
for i in range(Q):
    a,b = map(int,input().split())
    l.append(a)
    r.append(b)


for i in range(Q):
    if r[i] == l[i]:
        print(1)
    else:
        print(ruiseki[r[i]]-ruiseki[l[i]])

Submission status: Wrong Answer

Solution code:
list1=[1 for i in range(100001)]
list1[0]=0
list1[1]=0
for j in range(2,1000):
    if list1[j]==0:
        pass
    else:
        for k in range(2,1000):
            if j*k>1000:
                break
            else:
                list1[j*k]=0
#print(list1[:100])
list2=[0]
for l in range(1,100001):
    if list1[l]==0:
        list2.append(list2[l-1])
    else:
        if list1[int((l+1)/2)]==1:
            list2.append(list2[l-1]+1)
        else:
            list2.append(list2[l-1])
#print(list2[:100])
Q=int(input())
for x in range(Q):
    l,r=map(int,input().split())
    print(list2[r]-list2[l-1])

Submission status: Wrong Answer

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


def generate_prime(p_max):
    prime = set([2])
    for i in range(3, p_max + 1):
        for p in prime:
            if i % p == 0:
                break
            if p > int(math.sqrt(i)):
                prime.add(i)
                break
    return prime


def main():
    prime = generate_prime(10**5)
    prime2 = set()
    for p in prime:
        if (p + 1) / 2 in prime:
            prime2.add(p)
    ans = [0] * (10**5 + 1)
    for i in range(1, 10**5 + 1):
        if i in prime2:
            ans[i] = ans[i - 1] + 1
        else:
            ans[i] = ans[i - 1]

    q = int(input())
    queries = [[int(i) for i in input().split()] for _ in range(q)]
    for query in queries:
        print(ans[query[1]] - ans[query[0] - 1])


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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


def generate_prime(p_max):
    prime = set([2])
    for i in range(3, p_max + 1):
        for p in prime:
            if i % p == 0:
                break
            if p > math.sqrt(i):
                prime.add(i)
                break
    return prime


def main():
    prime = generate_prime(10**5)
    prime2 = set()
    for p in prime:
        if (p + 1) / 2 in prime:
            prime2.add(p)
    ans = [0] * (10**5 + 1)
    for i in range(1, 10**5 + 1):
        if i in prime2:
            ans[i] = ans[i - 1] + 1
        else:
            ans[i] = ans[i - 1]

    q = int(input())
    queries = [[int(i) for i in input().split()] for _ in range(q)]
    for query in queries:
        print(ans[query[1]] - ans[query[0] - 1])


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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


def generate_prime(p_max):
    prime = set([2])
    for i in range(3, p_max + 1):
        for p in prime:
            if i % p == 0:
                break
            if p > math.sqrt(i):
                prime.add(i)
                break
    return prime


def main():
    prime = generate_prime(10**5)
    prime2 = set()
    for p in prime:
        if ((p + 1) / 2 in prime):
            prime2.add(p)
    ans = [0]
    for i in range(1, 10**5 + 1):
        if (i in prime2):
            ans.append(ans[i - 1] + 1)
        else:
            ans.append(ans[i - 1])

    q = int(input())
    queries = [[int(i) for i in input().split()] for _ in range(q)]
    for query in queries:
        print(ans[query[1]] - ans[query[0] - 1])


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
maxnum = 10000

# エラトステネスのふるい
is_prime = [x for x in range(maxnum)]
for prime in is_prime:
    if prime == 0 or prime == 1:
        is_prime[prime] = 0
        continue
    for non_prime in range(prime * 2, maxnum, prime):
        is_prime[non_prime] = 0

is_like = [False] * maxnum
for i in range(maxnum):
    if (is_prime[i] and is_prime[(i + 1) // 2]):
        is_like[i] =  True

like_sum = [0] * maxnum
for i in range(3, maxnum):
    like_sum[i] = like_sum[i - 1]
    if (is_like[i]):
        like_sum[i] += 1

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

Submission status: Wrong Answer

Solution code:
maxnum = 10000

# エラトステネスのふるい
is_prime = [x for x in range(maxnum)]
for prime in is_prime:
    if prime == 0 or prime == 1:
        is_prime[prime] = 0
        continue
    for non_prime in range(prime * 2, maxnum, prime):
        is_prime[non_prime] = 0

is_like = [False] * maxnum
for i in range(maxnum):
    if (is_prime[i] and is_prime[(i + 1) // 2]):
        is_like[i] =  True

like_sum = [0] * maxnum
for i in range(3, maxnum):
    like_sum[i] = like_sum[i - 1]
    if (is_like[i]):
        like_sum[i] += 1

q = int(input())
for i in range(q):
    l, r = map(int, input().split())

Submission status: Wrong Answer

Solution code:
maxnum = 10000

# エラトステネスのふるい
is_prime = [x for x in range(maxnum)]
for prime in is_prime:
    if prime == 0 or prime == 1:
        is_prime[prime] = 0
        continue
    for non_prime in range(prime * 2, maxnum, prime):
        is_prime[non_prime] = 0

is_like = [False] * maxnum
for i in range(maxnum):
    if (is_prime[i] and is_prime[(i + 1) // 2]):
        is_like[i] =  True

like_sum = [0] * maxnum
for i in range(1, maxnum):
    like_sum[i] = like_sum[i - 1]
    if (is_like[i]):
        like_sum[i] += 1

q = int(input())
for i in range(q):
    l, r = map(int, input().split())
    print(r)

Submission status: Wrong Answer

Solution code:
import bisect
def prime_list(n):
    '''
    n未満の素数のリストを返す
    '''
    num = list(range(2, n))
    prime = []
    while num[0] ** 2 < n:
        p = num.pop(0)
        for j in range(2 * p, n, p):
            if j in num:
                num.remove(j)
        prime.append(p)
    prime += num
    return prime

Q = int(input())
queries = [list(map(int, input().split())) for _ in range(Q)]
primes = prime_list(2018)
prime_2017like = []
for prime in primes:
    if (prime + 1) // 2 in primes:
        prime_2017like.append(prime)
for i in range(Q):
    li, ri = queries[i]
    print(bisect.bisect_right(prime_2017like, ri) - bisect.bisect_right(prime_2017like, li - 1))