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 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 = [None] * 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)

Submission status: Wrong Answer

Solution code:
import sys
from bisect import bisect, bisect_left
sys.setrecursionlimit(10**6)
if sys.platform in (['ios','darwin','win32']):
	sys.stdin=open('Untitled.txt')
input = sys.stdin.readline
def INT(): return int(input())
def MAP(): return [int(s) for s in input().split()]

def get_sieve_of_eratosthenes(n):
	prime = [2]
	limit = int(n**0.5)
	data = [i + 1 for i in range(2, n, 2)]
	append = prime.append
	while True:
		p = data[0]
		if p > limit:
			return prime + data
		append(p)
		data = [e for e in data if e % p != 0]

def main():
	primes = get_sieve_of_eratosthenes(10**5)

	prime_dict = dict(zip(primes, [1]*len(primes)))
	prime_2017 = []
	append = prime_2017.append
	for k in prime_dict.keys():
		if (k+1)//2 in prime_dict:
			prime_2017.append(k)
	
	# print(prime_2017)

	Q = INT()
	for _ in range(Q):
		l, r = MAP()
		print(bisect(prime_2017, r)-bisect_left(prime_2017, l))
	print()

if __name__ == '__main__':
	main()

Submission status: Wrong Answer

Solution code:
import sys
from bisect import bisect, bisect_left
sys.setrecursionlimit(10**6)
if sys.platform in (['ios','darwin','win32']):
	sys.stdin=open('Untitled.txt')
input = sys.stdin.readline
def INT(): return int(input())
def MAP(): return [int(s) for s in input().split()]

def get_sieve_of_eratosthenes(n):
	prime = [2]
	limit = int(n**0.5)
	data = [i + 1 for i in range(2, n, 2)]
	append = prime.append
	while True:
		p = data[0]
		if p > limit:
			return prime + data
		append(p)
		data = [e for e in data if e % p != 0]

def main():
	primes = get_sieve_of_eratosthenes(10**5)

	prime_dict = dict(zip(primes, [1]*len(primes)))
	prime_2017 = []
	append = prime_2017.append
	for k in prime_dict.keys():
		if (k+1)//2 in prime_dict:
			prime_2017.append(k)
	
	# print(prime_2017)

	Q = INT()
	for _ in range(Q):
		l, r = MAP()
		print(bisect(prime_2017, r)-bisect_left(prime_2017, l))

if __name__ == '__main__':
	main()

Submission status: Wrong Answer

Solution code:
import sys
from bisect import bisect, bisect_left
sys.setrecursionlimit(10**6)
if sys.platform in (['ios','darwin','win32']):
	sys.stdin=open('Untitled.txt')
input = sys.stdin.readline
def INT(): return int(input())
def MAP(): return [int(s) for s in input().split()]

def get_sieve_of_eratosthenes(n):
	prime = [2]
	limit = int(n**0.5)
	data = [i + 1 for i in range(2, n, 2)]
	append = prime.append
	while True:
		p = data[0]
		if p > limit:
			return prime + data
		append(p)
		data = [e for e in data if e % p != 0]

def main():
	primes = get_sieve_of_eratosthenes(10**5)

	prime_dict = dict(zip(primes, [1]*len(primes)))
	prime_2017 = []
	for k in prime_dict.keys():
		if (k+1)//2 in prime_dict:
			prime_2017.append(k)
	
	# print(prime_2017)

	Q = INT()
	for _ in range(Q):
		l, r = MAP()
		print(bisect(prime_2017, r)-bisect_left(prime_2017, l))

if __name__ == '__main__':
	main()

Submission status: Wrong Answer

Solution code:

M=pow(10,5)

prime_sieve=[-1 for i in range(M+1)]
prime_sieve[0]=1
prime_sieve[1]=1

primes=[]
for i in range(M+1):
  if prime_sieve[i]==-1:
    primes.append(i)
    for j in range(2,(M+1)//i):
      prime_sieve[i*j]=1

rangesum=[0,0,0]
sum=0
for i in range(3,M+1):
  if prime_sieve[i]==-1:
    if prime_sieve[(i+1)//2]==-1:
       sum+=1
  rangesum.append(sum)

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

Submission status: Wrong Answer

Solution code:
from itertools import accumulate
import sys
input=sys.stdin.readline
def prm(x):
    if x == 1 or x == 4:
        return False
    for i in range(2,int(x**0.5+1)):
        if x%i==0:
            return False
    else:
        return True
def like2017(x):
    if x == 2:
        return False
    if prm(x) and prm((x-1)//2):
        return True
q=int(input())
l=[0]*(10**5+1)
for i in range(1,10**5+1):
    if like2017(i):
        l[i]=1
acl = list(accumulate(l))
for i in range(q):
    l,r=map(int,input().split())
    print(acl[r]-acl[l-1])

Submission status: Wrong Answer

Solution code:
m=10**5+1
is_prime=[1 for _ in range(m)]
is_prime[0]=0
is_prime[1]=0

#エラトステネスのふるい
for i in range(2,m):
	if is_prime[i]:
		for j in range(i*2,m,i):
			is_prime[j]=0

#2017like
a=[0 for _ in range(m)]
for i in range(m):
	if i % 2 == 0: continue
	if is_prime[i] == is_prime[(i+1)//2] == 1:
		a[i] = 1
		
#累積和
s=[0 for _ in range(m)]	
for i in range(1,m-1):
	s[i+1]=s[i]+a[i]
	
#query
q=int(input())
for i in range(q):
	l,r=map(int,input().split())
	print(s[r]-s[l-1])

Submission status: Wrong Answer

Solution code:
m=10**5+1
is_prime=[1 for _ in range(m)]
is_prime[0]=0
is_prime[1]=0

#エラトステネスのふるい
for i in range(2,m):
	if is_prime[i]:
		for j in range(i*2,m,i):
			is_prime[j]=0

#2017like
a=[0 for _ in range(m)]
for i in range(m):
	if i % 2 == 0: continue
	if is_prime[i] == is_prime[(i+1)//2]:
		a[i] = 1
		
#累積和
s=[0 for _ in range(m)]	
for i in range(1,m-1):
	s[i+1]=s[i]+a[i]
	
#query
q=int(input())
for i in range(q):
	l,r=map(int,input().split())
	print(s[r]-s[l])

Submission status: Wrong Answer

Solution code:
import sys
from collections import deque
from bisect import bisect_left, bisect_right
input = sys.stdin.readline
Q = int(input())
P = 10 ** 5
c1 = [i % 2 == 1 for i in range(P)]
c2 = [False for i in range(P)]
c1[2] = True
c2[3] = True
L = deque([])
for i in range(2, P):
    if c1[i]:
        ind = i*2-1
        if ind < P:
            c2[ind] = True
    if c1[i] and c2[i]:
        L.append(i)
        ind = i * 2
        while ind < P:
            c1[ind] = False
            ind += i

for q in range(Q):
    l, r = [int(x) for x in input().strip().split()]
    print(bisect_right(L, r) - bisect_left(L, l))

Submission status: Wrong Answer

Solution code:
import sys
from collections import deque
from bisect import bisect_left, bisect_right
input = sys.stdin.readline
Q = int(input())
P = 2 * 10 ** 5
c1 = [(i+1) % 2 == 1 for i in range(P)]
c2 = [False for i in range(P)]
c1[1] = True
c2[2] = True
L = deque([])
for i in range(1, P):
    if c1[i]:
        ind = (i+1)*2-2
        if ind < P:
            c2[ind] = True
    if c1[i] and c2[i]:
        L.append(i+1)
        ind = (i+1) * 2 - 1
        while ind < P:
            c1[ind] = False
            ind += (i+1)

for q in range(Q):
    l, r = [int(x) for x in input().strip().split()]
    print(bisect_right(L, r) - bisect_left(L, l))

Submission status: Wrong Answer

Solution code:
import sys
from collections import deque
from bisect import bisect_left, bisect_right
input = sys.stdin.readline
Q = int(input())
P = 2 * 10 ** 5
c1 = [(i+1) % 2 == 1 for i in range(P)]
c2 = [False for i in range(P)]
c2[2] = True
L = deque([])
for i in range(1, P):
    if c1[i]:
        ind = (i+1)*2-2
        if ind < P:
            c2[ind] = True
    if c1[i] and c2[i]:
        L.append(i+1)
        ind = (i+1) * 2 - 1
        while ind < P:
            c1[ind] = False
            ind += (i+1)

for q in range(Q):
    l, r = [int(x) for x in input().strip().split()]
    print(bisect_right(L, r) - bisect_left(L, l))

Submission status: Wrong Answer

Solution code:
import sys
from collections import deque
from bisect import bisect_left, bisect_right
input = sys.stdin.readline
Q = int(input())
P = 2 * 10 ** 5
c1 = [(i+1) % 2 == 1 for i in range(P)]
c2 = [False for i in range(P)]
c2[2] = True
L = deque([])
for i in range(2, P):
    if c1[i]:
        ind = (i+1)*2-2
        if ind < P:
            c2[ind] = True
    if c1[i] and c2[i]:
        L.append(i+1)
        ind = (i+1) * 2 - 1
        while ind < P:
            c1[ind] = False
            ind += (i+1)

for q in range(Q):
    l, r = [int(x) for x in input().strip().split()]
    print(bisect_right(L, r) - bisect_left(L, l))

Submission status: Wrong Answer

Solution code:
import sys
from collections import deque
from bisect import bisect_left
input = sys.stdin.readline
Q = int(input())
P = 2 * 10 ** 5
c1 = [(i+1) % 2 == 1 for i in range(P)]
c2 = [False for i in range(P)]
c2[2] = True
L = deque([])
for i in range(2, P):
    if c1[i]:
        ind = (i+1)*2-2
        if ind < P:
            c2[ind] = True
    if c1[i] and c2[i]:
        L.append(i+1)
        ind = (i+1) * 2 - 1
        while ind < P:
            c1[ind] = False
            ind += (i+1)

for q in range(Q):
    l, r = [int(x) for x in input().strip().split()]
    print(bisect_left(L, r) - bisect_left(L, l))

Submission status: Wrong Answer

Solution code:
import sys
from collections import deque
from bisect import bisect_left
input = sys.stdin.readline
Q = int(input())
P = 2 * 10 ** 5
c1 = [(i+1) % 2 == 1 for i in range(P)]
c2 = [False for i in range(P)]
c2[2] = True
L = deque([])
for i in range(2, P):
    if c1[i]:
        ind = (i+1)*2-2
        if ind < P:
            c2[ind] = True
    if c1[i] and c2[i]:
        L.append(i+1)
        ind = (i+1) * 2 - 1
        while ind < P:
            c1[ind] = False
            ind += (i+1)

for q in range(Q):
    l, r = [int(x) for x in input().strip().split()]
    print(bisect_left(L, r+1) - bisect_left(L, l))

Submission status: Wrong Answer

Solution code:
import sys
from collections import deque
from bisect import bisect_left
input = sys.stdin.readline
Q = int(input())
P = 10 ** 5
c1 = [(i+1) % 2 == 1 for i in range(P)]
c2 = [False for i in range(P)]
c2[2] = True
L = deque([])
for i in range(2, P):
    if c1[i]:
        ind = (i+1)*2-2
        if ind < P:
            c2[ind] = True
    if c1[i] and c2[i]:
        L.append(i+1)
        ind = (i+1) * 2 - 1
        while ind < P:
            c1[ind] = False
            ind += (i+1)

for q in range(Q):
    l, r = [int(x) for x in input().strip().split()]
    print(bisect_left(L, r+1) - bisect_left(L, l))

Submission status: Wrong Answer

Solution code:

from heapq import heappush, heappop, heapify
from collections import deque, defaultdict, Counter
import itertools
from itertools import permutations, combinations, accumulate
import sys
import bisect
import string
import math
import time
from fractions import gcd
#import random


def I(): return int(input())


def MI(): return map(int, input().split())


def LI(): return [int(i) for i in input().split()]


def LI_(): return [int(i)-1 for i in input().split()]


def StoI(): return [ord(i)-97 for i in input()]


def ItoS(nn): return chr(nn+97)


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


def show(*inp, end='\n'):
    if show_flg:
        print(*inp, end=end)


YN = ['Yes', 'No']
MOD = 10**9+7
inf = float('inf')
l_alp = string.ascii_lowercase
u_alp = string.ascii_uppercase
ts = time.time()
sys.setrecursionlimit(10**6)


# show_flg = True
show_flg = False


def is_prime(n):
    """
    nの素数判定
    :param int n:
    :rtype: Bool
    """
    if n == 1:
        return False
    for i in range(2, int(n**0.5)+1):
        if n % i == 0:
            return False
    return True


def main():
    Q = I()
    l = [0] * Q
    r = [0] * Q

    for i in range(Q):
        l[i], r[i] = MI()

    arr = []
    for i in range(10**5+1):
        if i % 2 == 1:
            arr.append(int(is_prime(i) and is_prime((i+1)//2)))
        else:
            arr.append(0)

    ARR = list(accumulate(arr))
    # print(arr[:100])
    # print(ARR[:100])

    for i in range(Q):
        if r[i] == l[i]:
            print(arr[l[i]])
        else:
            # print(r[i], l[i], ARR[r[i]], ARR[l[i]])
            print(ARR[r[i]] - ARR[l[i]])


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:

from heapq import heappush, heappop, heapify
from collections import deque, defaultdict, Counter
import itertools
from itertools import permutations, combinations, accumulate
import sys
import bisect
import string
import math
import time
from fractions import gcd
#import random


def I(): return int(input())


def MI(): return map(int, input().split())


def LI(): return [int(i) for i in input().split()]


def LI_(): return [int(i)-1 for i in input().split()]


def StoI(): return [ord(i)-97 for i in input()]


def ItoS(nn): return chr(nn+97)


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


def show(*inp, end='\n'):
    if show_flg:
        print(*inp, end=end)


YN = ['Yes', 'No']
MOD = 10**9+7
inf = float('inf')
l_alp = string.ascii_lowercase
u_alp = string.ascii_uppercase
ts = time.time()
sys.setrecursionlimit(10**6)


# show_flg = True
show_flg = False


def is_prime(n):
    """
    nの素数判定
    :param int n:
    :rtype: Bool
    """
    if n == 1:
        return False
    for i in range(2, int(n**0.5)+1):
        if n % i == 0:
            return False
    return True


def main():
    Q = I()
    l = [0] * Q
    r = [0] * Q
    dic = {}

    for i in range(Q):
        l[i], r[i] = MI()

    arr = []
    for i in range(10**5+1):
        if i % 2 == 1:
            arr.append(int(is_prime(i) and is_prime((i+1)//2)))
        else:
            arr.append(0)

    ARR = list(accumulate([0] + arr))

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


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
def main():
    q=int(input())
    aa=0
    bb=0
    a=[]
    b=[]
    ac=[]
    bc=[]
    for _ in range(q):
        aa,bb=map(int,input().split())
        a.append(aa)
        b.append(bb)
        # ac.append(aa)
        # bc.append(bb)

    # sorted(a)
    # sorted(b)
    bm=max(b)
    ans=[0]*100001
    flg=[0]*100001
    flg[0]=1
    flg[1]=1
    ans[2]=1
    ii=int((bm+1)**0.5)
    for i in range(2,100001):

        if flg[i]==0:
            flg[i]=1
            ans[i]=1
            for j in range(i,int(100001**0.5),i):
                flg[j]=1
    ans2=[]
    cnt=0
    for i in range(0,100001):
        if ans[i]==1 and ans[(i+1)//2]==1:
            cnt+=1
        ans2.append(cnt)
    # print(ans[:11])
    # print(ans2[:11])
    for i in range(0,q):
        print(ans2[b[i]]-ans2[a[i]-1])
    # print(ans[:8])
if __name__=='__main__':
    main()