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:
# -*- coding: utf-8 -*-
import math


def is_sosu(n):

    if n == 1 or n == 2:
        return True

    if n % 2 == 0:
        return False

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

    return True


def similar_to_2017(n):
    if is_sosu(n) and is_sosu((n + 1) / 2):
        return 1

    return 0


def main():
    q = int(input())
    in_target = [tuple(map(int, input().split())) for i in range(q)]

    similar_to_2017s = []
    for i in range(1, 100001):
        similar_to_2017s.append(similar_to_2017(i))

    for target in in_target:
        cnt = sum(similar_to_2017s[target[0] - 1:target[1]])

        print(cnt)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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


def is_sosu(n):

    if n == 1 or n == 2:
        return True

    if n % 2 == 0:
        return False

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

    return True


def similar_to_2017(n):
    return is_sosu(n) and is_sosu((n + 1) / 2)


def main():
    q = int(input())
    in_target = [tuple(map(int, input().split())) for i in range(q)]

    for target in in_target:
        cnt = 0
        for i in range(target[0], target[1] + 1):
            if similar_to_2017(i):
                cnt += 1

        print(cnt)



if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

n = 10 ** 5 + 2
is_prime = [True] * (n + 1)
is_prime[0] = False
is_prime[1] = False

for i in range(2, n + 1):
    if not is_prime[i]:
        continue

    for j in range(2 * i, n + 1, i):
        is_prime[j] = False

like = [False] * (n + 1)
for i in range(n):
    like[i] = is_prime[i] and is_prime[(i + 1) // 2]

cumsum = [0] * (n + 1)
for i in range(n):
    cumsum[i + 1] = cumsum[i] + like[i]

for l, r in X:
    print(cumsum[r] - cumsum[l - 1])

Submission status: Wrong Answer

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

n = 10 ** 5 + 2
is_prime = [True] * (n + 1)
is_prime[0] = False
is_prime[1] = False

for i in range(2, n + 1):
    if not is_prime[i]:
        continue

    for j in range(2 * i, n + 1, i):
        is_prime[j] = False

like = [False] * (n + 1)
for i in range(n):
    like[i] = is_prime[i] and is_prime[(i + 1) // 2]

cumsum = [0] * (n + 1)
for i in range(n):
    cumsum[i + 1] = cumsum[i] + like[i]

for l, r in X:
    print(cumsum[r] - cumsum[l])

Submission status: Wrong Answer

Solution code:
M=10**6
p=[1]*M
p[0]=p[1]=0
for i in range(2,4*10**4):
    if p[i]:
        for j in range(i*i,M,i):
            p[j]=0
C=[0]*M
for i in range(2,M):
    if p[i] and p[(i+1)//2]:
        C[i]=C[i-1]+1
    else:
        C[i]=C[i-1]
q=int(input())
for i in range(q):
    l,r=map(int,input().split())
    print(C[r]-C[l])

Submission status: Wrong Answer

Solution code:
# https://atcoder.jp/contests/abc084/tasks/abc084_d

q = int(input())
queries = []
for _ in range(q):
    l, r = map(int, input().split())
    queries.append((l, r))

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


for l, r in queries:
    ans = 0
    for x in range(l, r + 1):
        if is_prime(x) and is_prime((x + 1) // 2):
            ans += 1
    print(ans)

Submission status: Wrong Answer

Solution code:
import math

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


# 素数を表にする
primetable = [ 0 for i in range(3000) ]
for i in range(2, 3000):
    if is_prime(i):
        primetable[i] = 1
# 2017に似た数を表にする
like2017table = [ 0 for i in range(3000) ]
for i in range(2, 3000):
    if primetable[i] == 1 and \
        primetable[(i+1)//2] == 1:
        like2017table[i] = 1


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

for query in queries:
    begin = query[0]
    end = query[1]
    ans = sum(like2017table[begin:end+1])
    print(ans)

Submission status: Wrong Answer

Solution code:


# 素数一覧を作成
primes = [ i for i in range(2, 10001) ]

for i in range(10001):
    for j in range(i+1, 10001):
        try:
            if primes[j] % primes[i] == 0:
                primes.pop(j)
        except IndexError:
            break

# 素数を表にする
primetable = [ 0 for i in range(10001) ]
for prime in primes:
    primetable[prime] = 1

# 2017に似た数を表にする
like2017table = [ 0 for i in range(10001) ]
for i in range(2, 10001):
    if primetable[i] == 1 and \
        primetable[(i+1)//2]:
        like2017table[i] = 1

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

for query in queries:
    begin = query[0]
    end = query[1]
    ans = sum(like2017table[begin:end+1])
    print(ans)

Submission status: Wrong Answer

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

Q = int(input())
lr = []
l = []
r = []
for _ in range(Q):
    lr.append([int(x) for x in input().split()])
    l.append(lr[-1][0])
    r.append(lr[-1][1])

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

minl, maxr = min(l), max(r)
cumsum = [0] * (maxr + 1)

for i in range(1, maxr + 1, 2):
    if is_prime(i) and is_prime((i + 1) // 2) and i > 1:
        cumsum[i] = cumsum[i - 2] + 1
    elif i > 1:
        cumsum[i] = cumsum[i - 2]

for j in lr:
    l, r = j
    print(cumsum[r] - cumsum[l - 2])

Submission status: Wrong Answer

Solution code:
import bisect
q=int(input())
P=[2]
for i in range(3,10**5+2):
  for j in range(len(P)):
    if i%P[j]==0:
      break
    if j==len(P)-1:
      P.append(i)
p=set(P)
A=[]
for i in range(len(P)):
  if (P[i]+1)//2 in p:
    A.append(P[i])
for i in range(q):
  a,b=map(int,input().split())
  print(bisect.bisect_right(A,a,lo=0,hi=len(A))-bisect.bisect_left(A,b,lo=0,hi=len(A)))

Submission status: Wrong Answer

Solution code:
import sys
import bisect
readline = sys.stdin.buffer.readline

"""素数判定はこっち"""
def factrize(n):
    b = 2
    while b*b <= n:
        if n % b == 0:
            return False
        b = b+1
    return True

f = [2]

for i in range(3,10**5+2,2):
    if factrize(i):
        if factrize((i+1)//2):
            f.append(i)
q = int(readline())
for _ in range(q):
    l,r = map(int,readline().split())
    print(bisect.bisect(f,r)-bisect.bisect(f,l-1))

Submission status: Wrong Answer

Solution code:
def get_sieve_of_eratosthenes_new(n):
    import math
    if not isinstance(n, int):
        raise TypeError('n is int type.')
    if n < 2:
        raise ValueError('n is more than 2')
    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]

primelist=get_sieve_of_eratosthenes_new(10**5)
subprimelist=[(primelist[i]+1)//2 for i in range(0,len(primelist))]
primeset=set(primelist)
subprimeset=set(subprimelist)
real=list(primeset&subprimeset)
real=[2*real[i]-1 for i in range(0,len(real))]
real.sort()

Q=int(input())
l=[0]*Q
r=[0]*Q
for i in range(0,Q):
    l[i],r[i]=map(int,input().split())
for i in range(0,Q):
    s=0
    t=0
    start=0
    end=len(real)-1
    while end-start>1:
        test=(end+start)//2
        if real[test]>=l[i]:
            end=test
        else:
            start=test
    if real[start]>=l[i]:
        s=start
    else:
        s=end
    start=0
    end=len(real)-1
    while end-start>1:
        test=(end+start)//2
        if r[i]>=real[test]:
            start=test
        else:
            end=test
    if r[i]>=real[end]:
        t=end
    else:
        t=start
    print(t-s+1)

Submission status: Wrong Answer

Solution code:
def main():
    numbers = [0] * (10 ** 5 + 1)
    prime = [0] * (10 ** 5 + 1)
    numbers[1] = 1
    prime[1] = 1
    for i in range(2, 10 ** 5 + 1):
        if i % 2:
            is_prime = True
            j = 1
            while j * j <= i and is_prime:
                if (not i % j) and j > 1:
                    is_prime = False
                j += 1
            if is_prime:
                prime[i] = 1
            if is_prime and prime[(i + 1) // 2]:
                numbers[i] = numbers[i - 1] + 1
            else:
                numbers[i] = numbers[i - 1]
        else:
            numbers[i] = numbers[i - 1]
    query = int(input())
    for _ in range(query):
        left, right = map(int, input().split())
        print(numbers[right] - numbers[left - 1])


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
q=int(input())
M=100000

import math
def erato(n):
    prime=[]
    cnt=[0]*n
    limit=math.sqrt(n)
    data=[i+1 for i in range(1,n)]
    cnt=[0]*n
    while True:
        p=data[0]
        if limit<=p:
            return cnt
        prime.append(p)
        if (p+1)/2 in prime:
          cnt[p]=1
        data=[e for e in data if e%p!=0]

like=erato(M)
#print(like)
for i in range(1,M):
  if like[i]==1:
    like[i]=like[i-1]+1
  else:
    like[i]=like[i-1]
    
#print(like[2017],like[2016])
for i in range(q):
  l,r=map(int,input().split())
  print(like[r]-like[l-1])

Submission status: Wrong Answer

Solution code:
import math
import fractions
import bisect
import collections
import itertools
import heapq
import string
import sys
import copy
from collections import deque
sys.setrecursionlimit(10**7)
MOD = 10**9+7
def gcd(a,b):return fractions.gcd(a,b) #最大公約数
def lcm(a,b):return (a*b) // fractions.gcd(a,b) #最小公倍数
def iin(): return int(input()) #整数読み込み
def ifn(): return float(input()) #浮動小数点読み込み
def isn(): return input().split() #文字列読み込み
def imn(): return map(int, input().split()) #整数map取得
def fmn(): return map(float, input().split()) #浮動小数点map取得
def iln(): return list(map(int, input().split())) #整数リスト取得
def iln_s(): return sorted(iln()) # 昇順の整数リスト取得
def iln_r(): return sorted(iln(), reverse=True) # 降順の整数リスト取得
def fln(): return list(map(float, input().split())) # 浮動小数点リスト取得
def join(l, s=''): return s.join(l) #リストを文字列に変換
def perm(l, n): return itertools.permutations(l, n) # 順列取得
def perm_count(n, r): return math.factorial(n) // math.factorial(n-r) # 順列の総数
def comb(l, n): return itertools.combinations(l, n) # 組み合わせ取得
def comb_count(n, r): return math.factorial(n) // (math.factorial(n-r) * math.factorial(r)) #組み合わせの総数
def two_distance(a, b, c, d): return ((c-a)**2 + (d-b)**2)**.5 # 2点間の距離
def m_add(a,b): return (a+b) % MOD

def is_prime(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 is_prime

Q = iin()
lr = [iln() for _ in range(Q)]
max_v = 10**5
prime = is_prime(max_v)

c = [0 for _ in range(max_v+1)]
for i in range(max_v):
    c[i+1] = c[i]
    if i % 2 == 1 and prime[i] and prime[((i+1)//2)]: 
        c[i+1] += 1
for i in range(Q):
    l = lr[i][0]
    r = lr[i][1]
    if l == r: print(1 if prime[l] else 0)
    else: print(c[r] - c[l])

Submission status: Wrong Answer

Solution code:
import bisect
import sys


def make_primes(n):
    primes = [2]
    for i in range(3, n, 2):
        if all(i % prime != 0 for prime in primes):
            primes.append(i)
    return primes


def make_like2017():
    like2017 = [0]
    for idx in range(1, len(primes)):
        if (primes[idx] + 1) // 2 in primes:
            like2017.append(like2017[idx - 1] + 1)
        else:
            like2017.append(like2017[idx - 1])
    return like2017


def sol(l, r):
    if l == r:
        if l in primes and (l + 1) // 2 in primes:
            return 1
        else:
            return 0

    idx_l = bisect.bisect_left(primes, l)
    idx_r = bisect.bisect_left(primes, r)

    if idx_l == idx_r:
        return 0
    else:
        idx_l = max(0, idx_l - 1)
        idx_r = min(len(like2017s) - 1, idx_r)
        return like2017s[idx_r] - like2017s[idx_l]


N_MAX = 10000 # 10 ** 5

Q = int(sys.stdin.readline())
primes = make_primes(N_MAX)
like2017s = make_like2017()

for _ in range(Q):
    l, r = map(int, sys.stdin.readline().split())
    print(sol(l, r))

Submission status: Wrong Answer

Solution code:
import math
#----エラトステネスの篩--------
def get_primenumber(number):
    prime_list = []
    #2からnumberまでの数字をsearch_listに入れる
    prime_2007=[]
    j=0
    lr=[0]
    cnt=0

    search_list = list(range(2,number+1))
    while True:
      #search_listの先頭の値が√nの値を超えたら処理終了
      if search_list[0] > math.sqrt(number):
        #prime_listにsearch_listを結合
        prime_list.extend(search_list)
        break
      else:
        #search_listの先頭をprime_listに入れる
        head_num = search_list[0]
        prime_list.append(head_num)

        #search_listの先頭をpopする
        search_list.pop(0)
        #head_numの倍数を取り除く
        search_list = [num for num in search_list if num % head_num != 0]
    
    for item in prime_list:
        if (item+1)//2 in prime_list:
            prime_2007.append(item)

    for item in prime_2007:
        lr+=[cnt]*(item - j-1)
        cnt+=1
        j=item
        lr.append(cnt)
    #print(prime_2007)
    #print(lr)
    #return prime_list
    return(lr)


lrlr=get_primenumber(10**5+1)

result=[]
n=int(input())
for i in range(n):
    l,r=map(int,input().split())
    l=min(l,len(lrlr)-1)
    r=min(r,len(lrlr)-1)
    #print(l,r)
    #print(len(lrlr))

    result.append(lrlr[r]-lrlr[l-1])

for item in result:
    print(item)

Submission status: Wrong Answer

Solution code:
import math
#----エラトステネスの篩--------
def get_primenumber(number):
    prime_list = []
    #2からnumberまでの数字をsearch_listに入れる
    prime_2007=[]
    j=0
    lr=[0]
    cnt=0

    search_list = list(range(2,number+1))
    while True:
      #search_listの先頭の値が√nの値を超えたら処理終了
      if search_list[0] > math.sqrt(number):
        #prime_listにsearch_listを結合
        prime_list.extend(search_list)
        break
      else:
        #search_listの先頭をprime_listに入れる
        head_num = search_list[0]
        prime_list.append(head_num)

        if (head_num+1)//2 in prime_list:
            prime_2007.append(head_num)
            lr+=[cnt]*(head_num - j-1)
            cnt+=1
            j=head_num
            lr.append(cnt)


        #search_listの先頭をpopする
        search_list.pop(0)
        #head_numの倍数を取り除く
        search_list = [num for num in search_list if num % head_num != 0]
    #print(prime_2007)
    #print(lr)
    #return prime_list
    return(lr)


lrlr=get_primenumber(10**5+1)

result=[]
n=int(input())
for i in range(n):
    l,r=map(int,input().split())
    l=min(l,len(lrlr)-1)
    r=min(r,len(lrlr)-1)
    #print(l,r)
    #print(len(lrlr))

    result.append(lrlr[r]-lrlr[l-1])

for item in result:
    print(item)

Submission status: Wrong Answer

Solution code:
import math
#----エラトステネスの篩--------
def get_primenumber(number):
    prime_list = []
    #2からnumberまでの数字をsearch_listに入れる
    prime_2007=[]
    j=0
    lr=[0]
    cnt=0

    search_list = list(range(2,number+1))
    while True:
      #search_listの先頭の値が√nの値を超えたら処理終了
      if search_list[0] > math.sqrt(number):
        #prime_listにsearch_listを結合
        prime_list.extend(search_list)
        break
      else:
        #search_listの先頭をprime_listに入れる
        head_num = search_list[0]
        prime_list.append(head_num)

        if (head_num+1)//2 in prime_list:
            prime_2007.append(head_num)
            lr+=[cnt]*(head_num - j-1)
            cnt+=1
            j=head_num
            lr.append(cnt)


        #search_listの先頭をpopする
        search_list.pop(0)
        #head_numの倍数を取り除く
        search_list = [num for num in search_list if num % head_num != 0]
    #print(prime_2007)
    #print(lr)
    #return prime_list
    return(lr)


lrlr=get_primenumber(10**5+1)

n=int(input())
for i in range(n):
    l,r=map(int,input().split())
    l=min(l,len(lrlr)-1)
    r=min(r,len(lrlr)-1)
    #print(l,r)
    #print(lrlr)

    print(lrlr[r]-lrlr[l-1])

Submission status: Wrong Answer

Solution code:
q=int(input())

like2017={}

# 自然数m以下の素数を返す
def prime_numbers(m):
    # 素数を保持するset
    primes = set()

    # 2以上m以下の素数を数え上げる
    n = 2
    while n <= m:
        # 自身より小さい全ての素数で割り切れなければ、素数とみなせる
        if all(n % i != 0 for i in primes):
            primes.add(n)
        n += 1
    result=set()
    result.add(2)
    for item in primes:
      if item!=2:
        if (item+1)//2 in primes:
          result.add(item)
    
    rl={}
    rl[0]=0
    for i in range(1,m+1):
      if i in result:
        rl[i]=rl[i-1]+1
      else:
        rl[i]=rl[i-1]
    return rl

rlrl=prime_numbers(10**5+1)

#print(rlrl)
        
for item in range(q):
  l,r=map(int,input().split())
  print(rlrl[r]-rlrl[l]+1)

Submission status: Wrong Answer

Solution code:
m = 100010
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(m * 2+ 100)
n = int(input())

from bisect import bisect_left
def index(a, x):
    'Locate the leftmost value exactly equal to x'
    i = bisect_left(a, x)
    if i != len(a) and a[i] == x:
        return i
    raise ValueError

def do(x):
    if x in a and (x+1)//2 in a:
        return True
dat = [-1] * m
count = 0
for i in range(len(a)):
    if a[i] > m:
        break
    if do(a[i]):
        count += 1
    dat[a[i]] = count
c = -1
for i in range(m):
    if dat[i] != -1:
        c = dat[i]
    else:
        dat[i] = c
#print(dat)

for _ in range(n):
    l, r = map(int, input().split())
    print(dat[r+1] - dat[l+1])

Submission status: Wrong Answer

Solution code:
max_lr = 10 ** 5

sieve = [True] * (max_lr + 1)
sieve[0] = False
sieve[1] = False
for i in range(2, max_lr + 1):
    if sieve[i]:
        continue
    for j in range(i * i, max_lr + 1, i):
        sieve[j] = False

cs = [0] * (max_lr + 1)
for i in range(3, max_lr + 1, 2):
    if sieve[i] and sieve[(i + 1) // 2]:
        cs[i] = 1
for i in range(1, max_lr + 1):
    cs[i] += cs[i - 1]

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

Submission status: Wrong Answer

Solution code:
Q = int(input())
lr = []
maxr = 0
for i in range(Q):
    l,r = map(int,input().split())
    maxr = max(maxr,r)
    lr.append([l,r])
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 [2]+[i for i in range(3,n + 1) if is_prime[i] and is_prime[(i+1)//2]]
prime = primes(maxr)
import bisect
for l,r in lr:
    print(bisect.bisect_right(prime,r)-bisect.bisect_right(prime,l-1))

Submission status: Wrong Answer

Solution code:
Q = int(input())
lr = []
maxr = 0
for i in range(Q):
    l,r = map(int,input().split())
    maxr = max(maxr,r)
    lr.append([l,r])
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
    is_prime[2] = False
    return [2]+[i for i in range(3,n + 1) if is_prime[i] and is_prime[(i+1)//2]]
prime = primes(maxr)
import bisect
for l,r in lr:
    print(bisect.bisect_right(prime,r)-bisect.bisect_right(prime,l-1))

Submission status: Wrong Answer

Solution code:
# coding: utf-8
from bisect import bisect_left, bisect_right
def eratosthenes(N):
    # 素数判定
    flag = True
    for i in range(2, int(N**0.5) + 1):
        if N % i == 0:
            flag = False
            break
    return flag

def make_prime_nums(N):
    # Nまでの素数のリストを作成
    prime_tf = [True for _ in range(N+1)]
    prime_tf[0] = False
    prime_tf[1] = False
    for i in range(N+1):
        if prime_tf[i]:
            if eratosthenes(i):
                for j in range(i*2, N+1, i):
                    prime_tf[j] = False
    primes = [i for i in range(N+1) if prime_tf[i]]
    return primes

def make_prime_new(L):
    new_primes = []
    for l in L:
        tmp = (l+1) // 2
        if eratosthenes(tmp):
            new_primes.append(l)
    return new_primes

primes = make_prime_nums(10**5)
primes = make_prime_new(primes)[1:]
# print(primes)
N = int(input())
for _ in range(N):
    l, r = map(int, input().split())
    l_idx = bisect_left(primes, l)
    r_idx = bisect_left(primes, r)
    if l == r and l in primes:
        print(1)
    elif l == r and r not in primes:
        print(0)
    else:
        print(r_idx - l_idx)

Submission status: Wrong Answer

Solution code:
# coding: utf-8
from bisect import bisect_left, bisect_right
def eratosthenes(N):
    # 素数判定
    flag = True
    for i in range(2, int(N**0.5) + 1):
        if N % i == 0:
            flag = False
            break
    return flag

def make_prime_nums(N):
    # Nまでの素数のリストを作成
    prime_tf = [True for _ in range(N+1)]
    prime_tf[0] = False
    prime_tf[1] = False
    for i in range(N+1):
        if prime_tf[i]:
            if eratosthenes(i):
                for j in range(i*2, N+1, i):
                    prime_tf[j] = False
    primes = [i for i in range(N+1) if prime_tf[i]]
    return primes

def make_prime_new(L):
    new_primes = []
    for l in L:
        tmp = (l+1) // 2
        if eratosthenes(tmp):
            new_primes.append(l)
    return new_primes

primes = make_prime_nums(10**5)
primes = make_prime_new(primes)[1:]
# print(primes)
N = int(input())
for _ in range(N):
    l, r = map(int, input().split())
    l_idx = bisect_left(primes, l)
    r_idx = bisect_left(primes, r)
    if l == r and l in primes:
        print(1)
    elif l == r and r in primes:
        print(1)
    else:
        print(r_idx - l_idx)

Submission status: Wrong Answer

Solution code:
# coding: utf-8
from bisect import bisect_left, bisect_right
def eratosthenes(N):
    # 素数判定
    flag = True
    for i in range(2, int(N**0.5) + 1):
        if N % i == 0:
            flag = False
            break
    return flag

def make_prime_nums(N):
    # Nまでの素数のリストを作成
    prime_tf = [True for _ in range(N+1)]
    prime_tf[0] = False
    prime_tf[1] = False
    for i in range(N+1):
        if prime_tf[i]:
            if eratosthenes(i):
                for j in range(i*2, N+1, i):
                    prime_tf[j] = False
    primes = [i for i in range(N+1) if prime_tf[i]]
    return primes

def make_prime_new(L):
    new_primes = []
    for l in L:
        tmp = (l+1) // 2
        if eratosthenes(tmp):
            new_primes.append(l)
    return new_primes

primes = make_prime_nums(10**5)
primes = make_prime_new(primes)[1:]
# print(primes)
N = int(input())
for _ in range(N):
    l, r = map(int, input().split())
    l_idx = bisect_left(primes, l)
    r_idx = bisect_left(primes, r)
    if l == r and l in primes:
        print(1)
    else:
        print(r_idx - l_idx)

Submission status: Wrong Answer

Solution code:
# coding: utf-8
from bisect import bisect_left, bisect_right
def eratosthenes(N):
    # 素数判定
    flag = True
    for i in range(2, int(N**0.5) + 1):
        if N % i == 0:
            flag = False
            break
    return flag

def make_prime_nums(N):
    # Nまでの素数のリストを作成
    prime_tf = [True for _ in range(N+1)]
    prime_tf[0] = False
    prime_tf[1] = False
    for i in range(N+1):
        if prime_tf[i]:
            if eratosthenes(i):
                for j in range(i*2, N+1, i):
                    prime_tf[j] = False
    primes = [i for i in range(N+1) if prime_tf[i]]
    return primes

def make_prime_new(L):
    new_primes = []
    for l in L:
        tmp = (l+1) // 2
        if eratosthenes(tmp):
            new_primes.append(l)
    return new_primes

primes = make_prime_nums(10**5)
primes = make_prime_new(primes)[1:]
# print(primes)
N = int(input())
for _ in range(N):
    l, r = map(int, input().split())
    l_idx = bisect_left(primes, l)
    r_idx = bisect_left(primes, r)
    if l_idx == r_idx and l in primes:
        print(1)
    elif l_idx == r_idx and l not in primes:
        print(0)
    else:
        print(r_idx - l_idx)

Submission status: Wrong Answer

Solution code:

def main():
    n = int(input())

    sosuu_mask = sosuu()

    r = [0 for i in range(int(1e5+1))]
    l = [0 for i in range(int(1e5+1))]
    for i in range(len(r)-2,0,-1):
        r[i] += r[i+1] + sosuu_mask[i+1]
    for i in range(1,len(l)):
        l[i] += l[i-1] + sosuu_mask[i-1]
    _all = len([s for s in sosuu_mask if s==1])
    # print(sosuu_mask[:20])
    # print(_all)
    # print(r[:10])
    # print(l[:10])

    for i in range(n):
        a,b = list(map(int,input().split(' ')))
        # print(list(map(int,input().split(' '))))
        print(_all-l[a]-r[b])
    return 

def sosuu():
    ret = [1 for i in range(int(1e5+1))]
    ret[0]=0
    ret[1]=0
    for i in range(2,len(ret)):
        if ret[i]==0:
            continue
        else:
            for j in range(2*i,len(ret),i):
                ret[j] = 0
    ret2 = [s for s in ret]
    for i in range(len(ret)):
        if i%2==1 and ret[(i+1)//2]!=1:
            ret2[i]=0
    return ret2


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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

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


if __name__ == '__main__':
    Q=int(input())
    Queries=[list(map(int,input().split())) for i in range(Q)]

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

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
Q=int(input())
lr=[list(map(int,input().split())) for _ in range(Q)]
#素数リスト
n = 100000+100
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=list(primes)
#print(primes)
from bisect import bisect_left as bl
a=[0]*100001
for i in primes:
    s=bl(primes,(i+1)//2)
    if primes[s]==(i+1)//2:
        a[i]=1
#print(a)
for i in range(1,10001):
    a[i]+=a[i-1]

for i in range(Q):
    print(a[lr[i][1]]-a[lr[i][0]-1])

Submission status: Wrong Answer

Solution code:
prime = [3, 5]
for i in range(13, 102010, 12):
  r = int(i**(1/2))
  p = 0
  for j in range(2, r+1):
    if i % j == 0:
      p = 1
      break
  a = (i+1)//2
  r = int(a**(1/2))
  for j in range(2, r+1):
    if a % j == 0:
      p = 1
      break
  if p == 0:
    prime.append(i)
print(len(prime), prime[len(prime)-1])
Q = int(input())
for i in range(Q):
  L = list(map(int, input().split()))
  L[0] -= 1
  i = 0
  while L[0] >= prime[i]:
    i += 1
  j = 0
  while L[1] >= prime[j]:
    j += 1
  print(j-i)

Submission status: Wrong Answer

Solution code:
print(48-int(input()))

Submission status: Wrong Answer

Solution code:
# coding: utf-8
from bisect import bisect_left
def check(x):
    flag = True
    for i in range(2, int(x**0.5) + 1):
        if x % i == 0:
            flag = False
            break
    return flag

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]]
def primes_plus(l):
    # l: 素数の配列
    L = []
    for p in l:
        if check((p+1)//2):
            L.append(p)
    return L
l_primes = primes(10**6)
l_primes = primes_plus(l_primes)[1:]
# print(len(l_primes))
Q = int(input())
for i in range(Q):
    ans = 0
    l, r = map(int, input().split())
    l_idx = bisect_left(l_primes, l)
    r_idx = bisect_left(l_primes, r)
    # print(l_idx, r_idx)
    if l == r and l_idx == r_idx:
        print(1)
    else:
        print(r_idx - l_idx)
# print(l_primes)

Submission status: Wrong Answer

Solution code:
# coding: utf-8
from bisect import bisect_left
def check(x):
    flag = True
    for i in range(2, int(x**0.5) + 1):
        if x % i == 0:
            flag = False
            break
    return flag

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]]
def primes_plus(l):
    # l: 素数の配列
    L = []
    for p in l:
        if check((p+1)//2):
            L.append(p)
    return L
l_primes = primes(10**5)
l_primes = primes_plus(l_primes)[1:]
# print(len(l_primes))
Q = int(input())
for i in range(Q):
    ans = 0
    l, r = map(int, input().split())
    l_idx = bisect_left(l_primes, l)
    r_idx = bisect_left(l_primes, r)
    # print(l_idx, r_idx)
    if l == r and l_idx == r_idx:
        print(1)
    else:
        print(r_idx - l_idx)

Submission status: Wrong Answer

Solution code:
def is_prime(n):
    '''
    素数判定する
    '''
    if n == 1:
        return False
    for k in range(2, int(n**0.5) + 1):
        if n % k == 0:
            return False
    return True


Q = int(input())
prime_list = [False] * 100001
L = []
R = []
for _ in range(Q):
    l, r = map(int, input().split())
    L.append(l)
    R.append(r)
a = [0] * 100001
prime_list[2] = True
for i in range(1, 100001, 2):
    prime_list[i] = is_prime(i)
    if prime_list[i] and prime_list[(i+1)//2]:
        a[i] = a[i-2] + 1
    else:
        a[i] = a[i-2]
for i in range(Q):
    if L[i] == R[i]:
        print(prime_list[L[i]]*1)
    elif L[i] == 1:
        ans = a[R[i]] - a[L[i]]
        print(ans)
    else:
        ans = a[R[i]] - a[L[i]-2]
        print(ans)