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:
dp = [1]*(10**5+1) #エラトステネスの篩
dp[0],dp[1] = 0, 0
for i in range(2, 10**5+1):
    if dp[i] == 0:
        continue
    j = i
    while j + i <= 10**5:
        j += i
        if dp[j] == 1:
            dp[j] = 0

ni = [0]*(10**5+1) #2012_like check
for i in range(2, 10**5+1):
    if dp[i] == 1 and dp[(i+1)//2] == 1:
        ni[i] = 1

ru = [0]*(10**5+1)
for i in range(1, 10**5+1):
    ru[i] = ru[i-1] + ni[i]

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

Submission status: Wrong Answer

Solution code:
from math import ceil, sqrt

n = 10**5+200
hurui = [i for i in range(n+1)]
for i in range(2,ceil(sqrt(n))+1):
    for j in range(2,ceil(sqrt(i))+1):
        if i==2:
            continue
        if i%j == 0:
            break
    else:
        for k in range(i+i,n,i):
            if hurui[k] != k:
                continue
            hurui[k] = 0
    continue

hurui = [bool(i) for i in hurui]
poi = [False]*(n+1)
poi[1] = False
for i in range(n+1):
    # print(i)
    poi[i] = (i % 2 == 1 and hurui[i] and hurui[(i+1)//2])
#print(poi)
sa = [0]
for i in range(n+1):
    sa.append(sa[i]+poi[i])
#print(sa[:10])

#print(poi[2017])
#print(poi[:10])

q = int(input())
lr = [tuple(map(int,input().split())) for i in range(q)]
for li,ri in lr:
    print(sa[ri+1]-sa[li])

Submission status: Wrong Answer

Solution code:
from math import ceil, sqrt

n = 10**5+200
hurui = [i for i in range(n+1)]
for i in range(2,ceil(sqrt(n))+1):
    for j in range(2,ceil(sqrt(i))+1):
        if i==2:
            continue
        if i%j == 0:
            break
    else:
        for k in range(i+i,n,i):
            if hurui[k] != k:
                continue
            hurui[k] = 0
    continue

hurui = [bool(i) for i in hurui]
poi = [False]*(n+1)
for i in range(n+1):
    # print(i)
    poi[i] = (i % 2 == 1 and hurui[i] and hurui[(i+1)//2])
#print(poi)
sa = [0]
for i in range(n+1):
    sa.append(sa[i]+poi[i])
#print(sa[:10])

#print(poi[2017])
a = 0
for i in range(1,56):
    a += poi[i]
# print(a)

q = int(input())
lr = [tuple(map(int,input().split())) for i in range(q)]
for li,ri in lr:
    print(sa[ri+1]-sa[li])

Submission status: Wrong Answer

Solution code:
# 素数列挙
#############################################################
# 1~Nまでの整数の中で、素数であるものをリストで返す
def get_primes(N):
    primes = []
    for num in range(2, N + 1):
        for prime in primes:
            if num % prime == 0:
                break
        else:
            primes.append(num)
    return primes
#############################################################


primes = get_primes(10**5)
# print(primes)

nums = [0] * (10**5 + 1)
for i in range(1, 10**5 + 1, 2):
    if i in primes and (i + 1) // 2 in primes:
        nums[i] = 1

cumsum = [0]
for i in range(10**5 + 1):
    cumsum.append(cumsum[-1] + nums[i])

# print(cumsum)

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

Submission status: Wrong Answer

Solution code:
table=[True for i in range(100000+1)]
table[0]=False
table[1]=False
for i in range(2,400):
    for j in range(2,100000//i):
        table[i*j]=False
cnt=[0 for _ in range(100000+1)]
for i in range(1,100000+1):
    cnt[i]=cnt[i-1]
    if i%2==1 and table[i]==True and table[(i+1)//2]==True:
        cnt[i]+=1

Q=int(input())
lr=[list(map(int,input().split())) for _ in range(Q)]
for i in range(Q):
    print(cnt[lr[i][1]]-cnt[lr[i][0]-1])

Submission status: Wrong Answer

Solution code:
table=[True for i in range(100000+1)]
table[0]=False
table[1]=False
for i in range(2,400):
    for j in range(2,10000//i):
        table[i*j]=False
cnt=[0 for _ in range(100000+1)]
for i in range(1,100000+1):
    cnt[i]=cnt[i-1]
    if i%2==1 and table[i]==True and table[(i+1)//2]==True:
        cnt[i]+=1

Q=int(input())
lr=[list(map(int,input().split())) for _ in range(Q)]
for i in range(Q):
    print(cnt[lr[i][1]]-cnt[lr[i][0]-1])

Submission status: Wrong Answer

Solution code:
table=[True for i in range(100000+1)]
table[0]=False
table[1]=False
for i in range(2,400):
    for j in range(2,10000//i):
        table[i*j]=False
p=[]
for i in range(100000+1):
    if table[i]==True:
        p.append(i)
cnt=[0 for _ in range(100000+1)]
for i in range(1,100000+1):
    cnt[i]=cnt[i-1]
    if i%2==1 and table[i]==True and table[(i+1)//2]==True:
        cnt[i]+=1
Q=int(input())
for _ in range(Q):
    l,r=map(int,input().split())
    print(cnt[r]-cnt[l-1])

Submission status: Wrong Answer

Solution code:
table=[True for i in range(100000+1)]
table[0]=False
table[1]=False
for i in range(2,400):
    for j in range(2,10000//i):
        table[i*j]=False
p=[]
for i in range(100000+1):
    if table[i]==True:
        p.append(i)
sum=[0 for _ in range(100000+1)]
for i in range(1,100000+1):
    sum[i]+=sum[i-1]
    if table[i]==True and table[(i+1)//2]==True:
        sum[i]+=1
Q=int(input())
for _ in range(Q):
    l,r=map(int,input().split())
    print(sum[r]-sum[l-1])

Submission status: Wrong Answer

Solution code:
table=[True for i in range(100000+1)]
table[0]=False
table[1]=False
for i in range(2,1000):
    for j in range(2,100000//i):
        table[i*j]=False

sum=[0]
for i in range(1,100000+1):
    sum.append(sum[-1])
    if table[i]==True and table[(i+1)//2]==True:
        sum[-1]+=1
Q=int(input())
for _ in range(Q):
    l,r=map(int,input().split())
    print(sum[r]-sum[l-1])

Submission status: Wrong Answer

Solution code:
table=[True for i in range(100000+1)]
table[0]=False
table[1]=False
for i in range(2,400):
    for j in range(2,100000//i):
        table[i*j]=False
p=[]
for i in range(100000+1):
    if table[i]==True:
        p.append(i)
sum=[0]
for i in range(1,100000+1):
    sum.append(sum[-1])
    if table[i]==True and table[(i+1)//2]==True:
        sum[-1]+=1
Q=int(input())
for _ in range(Q):
    l,r=map(int,input().split())
    print(sum[r]-sum[l-1])

Submission status: Wrong Answer

Solution code:
table=[True for i in range(100000+1)]
table[0]=False
table[1]=False
for i in range(2,400):
    for j in range(2,10000//i):
        table[i*j]=False
p=[]
for i in range(100000+1):
    if table[i]==True:
        p.append(i)
sum=[0]
for i in range(1,100000+1):
    sum.append(sum[-1])
    if table[i]==True and table [(i+1)//2]:
        sum[-1]+=1
Q=int(input())
for _ in range(Q):
    l,r=map(int,input().split())
    print(sum[r]-sum[l-1])

Submission status: Wrong Answer

Solution code:
import math
import bisect
def get_prime(number):
    prime_list = []
    search_list = list(range(2,number + 1))
    while search_list[0] <= math.sqrt(number):
        head_num = search_list.pop(0)
        prime_list.append(head_num)
        search_list = [num for num in search_list if num % head_num != 0]
    prime_list.extend(search_list)
    return prime_list

l = get_prime(10000)
l2 = []
for i in range(len(l)):
    x = l[i]
    y = (x+1)//2
    if y in l:
        l2.append(x)

Q = int(input())
for i in range(Q):
    a,b = map(int, input().split())
    x = bisect.bisect_left(l2, a)
    y = bisect.bisect_right(l2, b)
    print(y-x)

Submission status: Wrong Answer

Solution code:
lis=[False]*100001
for i in range(2,10**3):
    if not lis[i]:
        for j in range(2*i,10**3,i):
            lis[j]=True
lis[1]=True
lis[0]=True
c=[0]*(100000+2)
for i in range(3,10**5+1,2):
    if (not lis[i]) and (not lis[(i+1)//2]):
        c[i]+=1
for i in range(3,10**5+1):
    c[i]+=c[i-1]
q=int(input())
for i in range(q):
    l,r=map(int,input().split())
    print(c[r]-c[l-1])

Submission status: Wrong Answer

Solution code:
lis=[False]*100003
for i in range(2,10**3):
    if not lis[i]:
        for j in range(2*i,10**3,i):
            lis[j]=True
lis[1]=True
lis[0]=True
c=[0]*(100000+2)
for i in range(3,10**5+1,2):
    if (not lis[i]) and (not lis[(i+1)//2]):
        c[i]+=1
for i in range(3,10**5+1):
    c[i]+=c[i-1]
q=int(input())
for i in range(q):
    l,r=map(int,input().split())
    print(c[r]-c[l-1])

Submission status: Wrong Answer

Solution code:
lis=[False]*100003
for i in range(2,10**3):
    if not lis[i]:
        for j in range(2*i,10**3,i):
            lis[j]=True
lis[1]=True
lis[0]=True
c=[0]*(100000+2)
for i in range(3,10**5+1,2):
    if (not lis[i]) and (not lis[(i+1)//2]):
        c[i]+=1
for i in range(3,10**5+1):
    c[i]+=c[i-1]
print(c)
q=int(input())
for i in range(q):
    l,r=map(int,input().split())
    print(c[r]-c[l-1])

Submission status: Wrong Answer

Solution code:
lis=[False]*100003
for i in range(2,10**3):
    if not lis[i]:
        for j in range(2*i,10**3,i):
            lis[j]=True
lis[1]=True
lis[0]=True
c=[0]*(100000+2)
c[2]=1
for i in range(3,10**5+1,2):
    if (not lis[i]) and (not lis[(i+1)//2]):
        c[i]+=1
for i in range(3,10**5+1):
    c[i]+=c[i-1]
q=int(input())
for i in range(q):
    l,r=map(int,input().split())
    print(c[r]-c[l-1])

Submission status: Wrong Answer

Solution code:
lis=[False]*100003
for i in range(2,10**3):
    if not lis[i]:
        for j in range(2*i,10**3,i):
            lis[j]=True
lis[1]=True
lis[0]=True
print(lis[:54])
c=[0]*(100000+2)
for i in range(3,10**5+1,2):
    if (not lis[i]) and (not lis[(i+1)//2]):
        c[i]+=1
for i in range(3,10**5+1):
    c[i]+=c[i-1]
q=int(input())
for i in range(q):
    l,r=map(int,input().split())
    print(c[r]-c[l-1])

Submission status: Wrong Answer

Solution code:
lis=[False]*100003
for i in range(2,10**5+1):
    if not lis[i]:
        for j in range(2*i,10**5+1,i):
            lis[j]=True
lis[1]=True
c=[0]*(100000+2)
c[2]=1
for i in range(3,10**5+1,2):
    if (not lis[i]) and (not lis[(i+1)//2]):
        c[i]+=1
for i in range(3,10**5+1):
    c[i]+=c[i-1]
q=int(input())
for i in range(q):
    l,r=map(int,input().split())
    print(c[r]-c[l-1])

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import sys
from collections import deque
from collections import defaultdict
import heapq
import collections
import itertools
import bisect
import copy
import math
sys.setrecursionlimit(10**6)

# lis_of_lis = [[] for _ in range(N)]


def zz(): return list(map(int, sys.stdin.readline().split()))


def z(): return int(sys.stdin.readline())


def S(): return sys.stdin.readline()[:-1]


def C(line): return [sys.stdin.readline() for _ in range(line)]


def get_sieve_of_eratosthenes(n):
    if not isinstance(n, int):
        raise TypeError('n is int type.')
    if n < 2:
        raise ValueError('n is more than 2')
    prime = [2]
    limit = int(n**0.5)
    data = [i + 1 for i in range(2, n, 2)]
    while True:
        p = data[0]
        if limit <= p:
            return prime + data
        prime.append(p)
        data = [e for e in data if e % p != 0]


max_ = pow(10, 5) + 2
primes = get_sieve_of_eratosthenes(max_)
num_lile2017 = [0]*max_
primes2 = []
for prime in primes:
    primes2.append(2*prime-1)
like2017 = sorted(list(set(primes2) & set(primes)))
idx = 0
for i in range(max_):
    if (like2017[idx] < i and i < like2017[-1]):
        idx += 1
    num_lile2017[i] += idx

Q = z()
for i in range(Q):
    l, r = zz()
    print(num_lile2017[r+1] - num_lile2017[l-1])

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import sys
from collections import deque
from collections import defaultdict
import heapq
import collections
import itertools
import bisect
import copy
import math
sys.setrecursionlimit(10**6)

# lis_of_lis = [[] for _ in range(N)]


def zz(): return list(map(int, sys.stdin.readline().split()))


def z(): return int(sys.stdin.readline())


def S(): return sys.stdin.readline()[:-1]


def C(line): return [sys.stdin.readline() for _ in range(line)]


def get_sieve_of_eratosthenes(n):
    if not isinstance(n, int):
        raise TypeError('n is int type.')
    if n < 2:
        raise ValueError('n is more than 2')
    prime = [2]
    limit = int(n**0.5)
    data = [i + 1 for i in range(2, n, 2)]
    while True:
        p = data[0]
        if limit <= p:
            return prime + data
        prime.append(p)
        data = [e for e in data if e % p != 0]


max_ = pow(10, 5) + 2
primes = get_sieve_of_eratosthenes(max_)
num_lile2017 = [0]*max_
primes2 = []
for prime in primes:
    primes2.append(2*prime-1)
like2017 = sorted(list(set(primes2) & set(primes)))
idx = 0
for i in range(max_):
    if (like2017[idx] < i and i < like2017[-1]):
        idx += 1
    num_lile2017[i] += idx

Q = z()
print(num_lile2017[4])
for i in range(Q):
    l, r = zz()
    print(num_lile2017[r+1] - num_lile2017[l-1])

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import sys
from collections import deque
from collections import defaultdict
import heapq
import collections
import itertools
import bisect
import copy
import math
sys.setrecursionlimit(10**6)

# lis_of_lis = [[] for _ in range(N)]


def zz(): return list(map(int, sys.stdin.readline().split()))


def z(): return int(sys.stdin.readline())


def S(): return sys.stdin.readline()[:-1]


def C(line): return [sys.stdin.readline() for _ in range(line)]


def get_sieve_of_eratosthenes(n):
    if not isinstance(n, int):
        raise TypeError('n is int type.')
    if n < 2:
        raise ValueError('n is more than 2')
    prime = [2]
    limit = int(n**0.5)
    data = [i + 1 for i in range(2, n, 2)]
    while True:
        p = data[0]
        if limit <= p:
            return prime + data
        prime.append(p)
        data = [e for e in data if e % p != 0]


max_ = pow(10, 5) + 2
primes = get_sieve_of_eratosthenes(max_)
num_lile2017 = [0]*max_
primes2 = []
for prime in primes:
    primes2.append(2*prime-1)
like2017 = sorted(list(set(primes2) & set(primes)))
idx = 0
for i in range(max_):
    if (like2017[idx] < i and i < like2017[-1]):
        idx += 1
    num_lile2017[i] += idx

Q = z()
for i in range(Q):
    l, r = zz()
    print(num_lile2017[r+1] - num_lile2017[l])

Submission status: Wrong Answer

Solution code:
Q = int(input())

lim = 10**5+10
p = [True]*lim
p[0] = False
p[1] = False
for i in range(2, int(lim**0.5)+1):
    for j in range(i*2, 10**5+1, i):
        p[j] = False

y = [0]*lim
for i in range(3, lim, 2):
    y[i] = y[i-2]
    if p[i] and p[(i+1)//2]:
        y[i] += 1

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

Submission status: Wrong Answer

Solution code:
q=int(input())

#prime table
prime=[0 for i in range(10**5+5)]
for i in range(2,10**5+5):
  j=1
  if not prime[i]:
    while j*i<=10**5+4:
      prime[j*i]=i
      j+=1

like2017=[0 for i in range(10**5+5)]
for i in range(3,10**5+5,2):
  j=(i+1)//2
  if i==prime[i] and j==prime[j]:
    like2017[i]=1

like2017sum=[0 for i in range(10**5+5)]
for i in range(10**5+4):
  like2017sum[i+1]=like2017sum[i]+like2017[i+1]

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

Submission status: Wrong Answer

Solution code:
from math import sqrt
import bisect


def is_prime(num):
    if num < 2:
        return True
    elif num == 2:
        return True
    elif num % 2 == 0:
        return False

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

    return True


def solve(query):
    ans = []
    al = []
    for i in range(3, 10**5+1, 2):
        if is_prime(i) and is_prime((i+1)//2):
            al.append(i)

    for q in query:
        if is_prime(q[0]) and is_prime((q[0]+1)//2):
            l_ind = bisect.bisect_right(al, q[0]) - 1
        else:
            l_ind = bisect.bisect_right(al, q[0])
        if is_prime(q[1]) and is_prime((q[1]+1)//2):
            r_ind = bisect.bisect_left(al, q[1])
        else:
            r_ind = bisect.bisect_left(al, q[1]) - 1
        ans.append(r_ind-l_ind+1)

    return ans


if __name__ == "__main__":
    Q = int(input())
    query = [list(map(int, input().split())) for _ in range(Q)]

    ans = solve(query)

    for a in ans:
        print(a)

Submission status: Wrong Answer

Solution code:
# nまでの自然数が素数かどうかを表すリストを返す
def makePrimeChecker(n):
	isPrime = [True] * (n + 1)
	isPrime[0] = False
	isPrime[1] = False
	for i in range(2, int(n ** 0.5) + 1):
		if isPrime[i]:
			for j in range(i * i, n + 1, i):
				isPrime[j] = False
	return isPrime



isPrime = makePrimeChecker(100000)
Q = int(input())
L=[0]

#2017nunberの累積和
for i in range(100000):
	if i&1==1 and isPrime[i] and isPrime[(i+1)//2]:
		L.append(L[-1]+1)
	else:
		L.append(L[-1])

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

Submission status: Wrong Answer

Solution code:
import numpy as np

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

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

MaxQ = 10**5+1
Q = int(input())
lr = [list(map(int,input().split())) for _ in range(Q)]

a = [0]*MaxQ
s = [0]*MaxQ
prime = isPrime_np(MaxQ)
pset = set(prime)
for p in prime:
    if (p+1)/2 in pset:
        a[p] = 1

ans = []
s = np.cumsum(a)
    
for l,r in lr:
    ans.append(s[r+1] - s[l])
print(*ans,sep="\n")

Submission status: Wrong Answer

Solution code:
import numpy as np

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

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

MaxQ = 10**5+1
Q = int(input())
lr = [list(map(int,input().split())) for _ in range(Q)]

a = [0]*MaxQ
s = [0]*MaxQ
prime = isPrime_np(MaxQ)
pset = set(prime)
for p in prime:
    if (p+1)/2 in pset:
        a[p] = 1

ans = []
for i in range(MaxQ-1):
    s[i+1] = s[i] + a[i]
    
for l,r in lr:
    ans.append(s[r] - s[l])
print(*ans,sep="\n")

Submission status: Wrong Answer

Solution code:

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

for i in range(2,100010):
    if isprime[i]==True:
        if isprime[(i+1)//2]==True:
            count+=1
    
    S[i]=count
        
                
    

    
for k in range(N):
    l,r=map(int,input().split())
    if l!=r:
        print(S[r]-S[l-1])
    else:
        if S[r]!=S[r-1]:
            print(1)

Submission status: Wrong Answer

Solution code:
N = int(input())
import math
def decide_sosuu(n):
    if n == 1:
        return False
    else:
        for i in range(2, int(math.sqrt(n)) + 1):
            if n % i == 0:
                return False
    return True
for _ in range(N):
    cnt = 0
    l, r = map(int, input().split())
    for i in range(l, r+1):
        if decide_sosuu(i):
            if decide_sosuu((i+1)/2):
                cnt += 1
    print(cnt)

Submission status: Wrong Answer

Solution code:
#クエリにO(1)で返すためのテーブルを用意
import numpy as np
MAX = int(10e5+1)
List = list(range(2,MAX))
P = set()
while True:
    p = List[0]
    if p >= np.sqrt(MAX): break
    P.add(p)
    List = [x for x in List if x % p != 0]
Ans = [0] * MAX
cnt = 0
for i in range(1,MAX):
    if i in P and (i+1)//2 in P:
        cnt += 1
    Ans[i] = cnt

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

Submission status: Wrong Answer

Solution code:
import sys


def like2017(N):

    D = [True] * (N + 1)
    L = [0] * (N + 1)

    D[0] = False
    D[1] = False

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

        for j in range(2, (N + 1) // i):
            D[i * j] = False

    cnt = 0
    for i in range(1, N + 1):
        if D[i] and D[(i + 1) // 2] and i % 2 == 1:
            cnt += 1
        L[i] = cnt

    return L


def main():
    Q = int(sys.stdin.readline().rstrip())  # クエリ数

    L = like2017(10**5)

    for _ in range(Q):
        l, r = map(int, sys.stdin.readline().rstrip().split())
        print(L[r] - L[l - 1])


main()

Submission status: Wrong Answer

Solution code:
import sys


def like2017(N):

    D = [True] * (N + 1)
    L = [0] * (N + 1)

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

        for j in range(2, (N + 1) // i):
            D[i * j] = False

    cnt = 0
    for i in range(2, N + 1):
        if D[i] and D[(i + 1) // 2]:
            cnt += 1
        L[i] = cnt

    return L


def main():
    Q = int(sys.stdin.readline().rstrip())  # クエリ数

    L = like2017(10**5)

    for _ in range(Q):
        l, r = map(int, sys.stdin.readline().rstrip().split())
        print(L[r] - L[l - 1])


main()

Submission status: Wrong Answer

Solution code:
import itertools
import copy
q=int(input())
qr=[list(map(int,input().split())) for i in range(q)]
sosu=[1]*(10**5+1)
sosu[0]=0
sosu[1]=0
k=2
while k<(10**5+1)**0.5+1:
  for i in range(2*k,10**5+1,k):
    sosu[i]=0
  if k==2:
    k+=1
  else:
    k+=2
    
n=[0]*(10**5+1)
for i in range(1,len(sosu)):
  if i%2==1 and sosu[i]==1 and sosu[(i+1)//2]==1:
    n[i]=1
print(n)
ans=list(itertools.accumulate(n))
for i in range(q):
  print(ans[qr[i][1]]-ans[qr[i][0]-1])

Submission status: Wrong Answer

Solution code:
import itertools
import copy
q=int(input())
qr=[list(map(int,input().split())) for i in range(q)]
n=[1]*(10**5+1)
n[0]=0
k=2
while k<(10**5+1)**0.5+1:
  for i in range(2*k,10**5+1,k):
    n[i]=0
  if k==2:
    k+=1
  else:
    k+=2
d=copy.deepcopy(n)
n[2]=0
for i in range(1,len(d)):
  if n[i]==1 and d[(i+1)//2]==0:
    n[i]=0

ans=list(itertools.accumulate(n))
for i in range(q):
  print(ans[qr[i][1]]-ans[qr[i][0]-1])

Submission status: Wrong Answer

Solution code:
import itertools
import copy
q=int(input())
qr=[list(map(int,input().split())) for i in range(q)]
n=[1]*(10**5+1)
n[0]=0
k=2
while k<(10**5+1)**0.5+1:
  for i in range(2*k,10**5+1,k):
    n[i]=0
  if k==2:
    k+=1
  else:
    k+=2
n[2]=0
d=copy.deepcopy(n)
for i in range(1,len(d)):
  if n[i]==1 and d[(i+1)//2]==0:
    n[i]=0
ans=list(itertools.accumulate(n))
for i in range(q):
  print(ans[qr[i][1]]-ans[qr[i][0]-1])

Submission status: Wrong Answer

Solution code:
import itertools
import copy
q=int(input())
qr=[list(map(int,input().split())) for i in range(q)]
n=[1]*(10**5+1)
n[0]=0
k=2
while k<(10**5+1)**0.5+1:
  for i in range(2*k,10**5+1,k):
    n[i]=0
  if k==2:
    k+=1
  else:
    k+=2
k=copy.deepcopy(n)
for i in range(1,len(n)):
  if i%2==1 and k[i]==1 and k[(i+1)//2]==0:
    n[i]=0
    
#print(n)
ans=list(itertools.accumulate(n))
for i in range(q):
  print(ans[qr[i][1]]-ans[qr[i][0]-1])

Submission status: Wrong Answer

Solution code:
import math

def primes(x):
    if x < 2: return []

    primes = [i for i in range(x)]
    primes[1] = 0 # 1は素数ではない

    # エラトステネスのふるい
    for prime in primes:
        if prime > math.sqrt(x): break
        if prime == 0: continue
        for non_prime in range(2 * prime, x, prime): primes[non_prime] = 0

    return [prime for prime in primes if prime != 0]

pr = primes(100000)
d=[0]*100001
ans=[0]*100001

for j in pr:
    d[j]=1

for k in pr:
    tmp = (k+1)//2
    if d[tmp]==1:
        ans[k]=1

import numpy as np
cum = np.cumsum(ans)

q=int(input())
for _ in range(q):
    l,r = map(int,input().split())
    i1 = cum[l-1]
    i2 = cum[r]
    if l==r and d[l]==1:
        print(1)
    elif l ==r and d[l]==0:
        print(0)
    else:
        print(i2 - i1)

Submission status: Wrong Answer

Solution code:
import math

def primes(x):
    if x < 2: return []

    primes = [i for i in range(x)]
    primes[1] = 0 # 1は素数ではない

    # エラトステネスのふるい
    for prime in primes:
        if prime > math.sqrt(x): break
        if prime == 0: continue
        for non_prime in range(2 * prime, x, prime): primes[non_prime] = 0

    return [prime for prime in primes if prime != 0]

pr = primes(100000)
d=[0]*100001
ans=[0]*100001

for j in pr:
    d[j]=1

for k in pr:
    tmp = (k+1)//2
    if d[tmp]==1:
        ans[k]=1

import numpy as np
cum = np.cumsum(ans)

q=int(input())
for _ in range(q):
    l,r = map(int,input().split())
    i1 = cum[l-1]
    i2 = cum[r-1]
    if l==r and d[l]==1:
        print(1)
    elif l ==r and d[l]==0:
        print(0)
    else:
        print(i2 - i1)

Submission status: Wrong Answer

Solution code:
import sys
def input(): return sys.stdin.readline().strip()
def mapint(): return map(int, input().split())
sys.setrecursionlimit(10**9)

s = set()
for i in range(2, 10**5+5):
    if i in s:
        continue
    cnt = 2
    while i*cnt<=10**5+5:
        s.add(i*cnt)
        cnt += 1

from itertools import accumulate

lis = [0]*(10**5+5)
for i in range(1, 10**5+5, 2):
    if not i in s and not (i+1)//2 in s:
        lis[i] = 1

lis = list(accumulate(lis))
Q = int(input())
for _ in range(Q):
    l, r = mapint()
    print(lis[r]-lis[l-1])

Submission status: Wrong Answer

Solution code:
import math

def primes(x):
    if x < 2: return []

    primes = [i for i in range(x)]
    primes[1] = 0 # 1は素数ではない

    # エラトステネスのふるい
    for prime in primes:
        if prime > math.sqrt(x): break
        if prime == 0: continue
        for non_prime in range(2 * prime, x, prime): primes[non_prime] = 0

    return [prime for prime in primes if prime != 0]

pr = primes(100000)
d=[0]*100001
ans=[0]*100001

for j in pr:
    d[j]=1

for k in pr:
    tmp = (k+1)//2
    if d[tmp]==1:
        ans[k]=1

import numpy as np
cum = np.cumsum(ans)

q=int(input())
for _ in range(q):
    l,r = map(int,input().split())
    i1 = cum[l-1]
    i2 = cum[r-1]
    if l==r and d[l-1]==1:
        print(i2-i1+1)
    else:
        print(i2-i1)

Submission status: Wrong Answer

Solution code:
import math

def primes(x):
    if x < 2: return []

    primes = [i for i in range(x)]
    primes[1] = 0 # 1は素数ではない

    # エラトステネスのふるい
    for prime in primes:
        if prime > math.sqrt(x): break
        if prime == 0: continue
        for non_prime in range(2 * prime, x, prime): primes[non_prime] = 0

    return [prime for prime in primes if prime != 0]

pr = primes(100000)


d=[0]*100001

for j in pr:
    d[j]=1

ans=[0]*100001
for k in pr:
    tmp = (k+1)//2
    if d[tmp]==1:
        ans[k]=1

import numpy as np
cum = np.cumsum(ans)

q=int(input())
for _ in range(q):
    l,r = map(int,input().split())
    i1 = cum[l-1]
    i2 = cum[r-1]
    if l==r and d[l-1]==1:
        print(1)
    else:
        print(i2-i1)

Submission status: Wrong Answer

Solution code:
import math

def primes(x):
    if x < 2: return []

    primes = [i for i in range(x)]
    primes[1] = 0 # 1は素数ではない

    # エラトステネスのふるい
    for prime in primes:
        if prime > math.sqrt(x): break
        if prime == 0: continue
        for non_prime in range(2 * prime, x, prime): primes[non_prime] = 0

    return [prime for prime in primes if prime != 0]

pr = primes(100000)


d=[0]*100001

for j in pr:
    d[j]=1

ans=[0]*100001
for k in pr:
    tmp = (k+1)//2
    if d[tmp]==1:
        ans[k]=1

import numpy as np
cum = np.cumsum(ans)

q=int(input())
for _ in range(q):
    l,r = map(int,input().split())
    i1 = cum[l-1]
    i2 = cum[r-1]
    if l==r and d[l]==1:
        print(1)
    else:
        print(i2-i1)

Submission status: Wrong Answer

Solution code:
x=int(input())
a=list(range(2,3000))
for i in  range(len(a)):
    for k in range(len(a)):
        if  a[i]<a[k] and a[i]!=0 and a[k]%a[i]==0:
            a[k]=0
q=[i for i in a if i!=0]
ans=[0]*(10**5+1)
for i in range(10**5):
    ans[i+1]=ans[i]+(1 if i+1 in q and (i+1+1)//2 in q else 0 )
for i in range(x):
    l,r = map(int,input().split())	
    print(ans[r]-ans[l-1])

Submission status: Wrong Answer

Solution code:
x=int(input())
a=list(range(2,3000))
for i in  range(len(a)):
    for k in range(len(a)):
        if  a[i]<a[k] and a[i]!=0 and a[k]%a[i]==0:
            a[k]=0
q=[i for i in a if i!=0]
ans=[0]*(10**5+1)
for i in range(10**5):
    ans[i+1]=ans[i]+(1 if i+1 in q and (i+1+1)//2 in q else 0 )
for i in range(x):
    l,r = map(int,input().split())	
    if l==r:
        print(1 if l in q else 0)
    else:
        print(ans[r]-ans[l-1])

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
import math

def eratosthenes(n):
    prime_list = []
    num_list=[i for i in range(2, n+1)]
    limit = math.sqrt(n)
    while True:
        if limit <= num_list[0]:
            return prime_list + num_list
        prime_list.append(num_list[0])
        num_list = [e for e in num_list if e % num_list[0] != 0]

er_list = eratosthenes(100000)
count = [0 for i in range(100000)]
j = 0
for i in range(er_list[-1]):
    if i == er_list[j]:
        j += 1
        if (i+1)//2 in er_list:
            count[i] = 1 
            
for i in range(1,len(count)):
    count[i]  = count[i]+count[i-1]
    
Q = int(input())
for i in range(Q):
    l, r = map(int, input().split())
    print(count[r-1]-count[l-1])

Submission status: Wrong Answer

Solution code:
import math

q = int(input())
odds_list = [[0]*2 for _ in range(q)]
for i in range(q):
    odds_list[i][0],odds_list[i][1] = map(int,input().split())
def isPrime(n):
  if n == 2:
    return True
  if n % 2 == 0:
    return False

  # nの平方根まで計算する
  m = math.floor(math.sqrt(n)) + 1
  for p in range(3, m, 2):
      if n % p == 0:
        return False
  return True

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

Submission status: Wrong Answer

Solution code:
import math

q = int(input())
odds_list = [[0]*2 for _ in range(q)]
for i in range(q):
    odds_list[i][0],odds_list[i][1] = map(int,input().split())
def isPrime(n):
  if n == 2:
    return True
  if n % 2 == 0:
    return False

  # nの平方根まで計算する
  m = math.floor(math.sqrt(n)) + 1
  for p in range(3, m, 2):
      if n % p == 0:
        return False
  return True

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