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: Accepted

Solution code:
n=10**5
a=[1]*(n+1)
for x in range(2,int(n**0.5)+1):
    if a[x]:
        for i in range(x*x,n+1,x):
            a[i]=0
a[0]=a[1]=0
for x in range((n+1)//2,0,-1):
    if a[x] == 0:
        a[2*x-1] = 0
m=a[2]=0
for x in range(n+1):
    m += a[x]
    a[x] = m

lr=[input() for _ in [0]*int(input())]
for x in lr:
    l,r = map(int,x.split())
    print(a[r]-a[l-1])

Submission status: Accepted

Solution code:
Q = int(input())
MAX_N = 100000
ps = [False] * MAX_N
ps[2] = True
for i in range(3, MAX_N, 2):
    flg = True
    for j in range(2, MAX_N):
        if not flg or  j * j > i:
            break
        elif not ps[j]:
            continue
        flg = flg and i % j != 0
    ps[i] = flg

like = [False] * MAX_N
for i in range(3, MAX_N, 2):
    like[i] = ps[i] and ps[(i+1)//2]

ss = [0] * MAX_N
for i in range(2, MAX_N-1):
    if like[i]:
        ss[i] += 1
    ss[i+1] += ss[i]

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

Submission status: Accepted

Solution code:
import math
def sieve_of_erastosthenes(num):
    input_list = [0 if i % 2 == 0 or i % 3 == 0 or i % 5 == 0 else 1 for i in range(num)]
    input_list[0] = input_list[1] = 0
    input_list[2] = input_list[3] = input_list[5] = 1
    sqrt = math.sqrt(num)
    for serial in range(3, num, 2):
        if serial >= sqrt:
            return input_list
        for s in range(serial ** 2, num, serial): 
            input_list[s] = 0
q = int(input())
l_list = []
r_list = []
for i in range(q):
    l, r = map(int, input().split())
    l_list.append(l)
    r_list.append(r)
minval = min(l_list)
maxval = max(r_list)
sieve = sieve_of_erastosthenes(maxval+1)
def is_prime(x):
    return sieve[x]
def is_like2017(x):
    return is_prime(x) * is_prime(int((x+1)/2))
like2017 = list(range(maxval+1))
for i in like2017:
    like2017[i] = is_like2017(i)

integral = like2017
for i in range(1, len(integral)):
    integral[i] = integral[i] + integral[i-1]
for l, r in zip(l_list, r_list):
    print(integral[r] - integral[l-1])

Submission status: Accepted

Solution code:
import math
def is_prime(n):
    if n < 2:
        return False
    if n % 2 == 0 and n > 2:
        return False
    for i in range(3, int(math.sqrt(n)) + 1, 2):
        if n % i == 0:
            return False
    return True

Q= 100000

primes = [is_prime(n) and is_prime((n+1) / 2) for n in range(0, Q+1)]

accu=[0] * (Q+1)
for i in range(1, Q+1):
    #print(i)
    accu[i] = accu[i-1]
    if primes[i]:
        accu[i] = accu[i]+ 1

n = int(input())
for k in range(n):
    l,r = map(int, input().strip().split(' '))
    print("%d" % (accu[r] - accu[l-1]))

Submission status: Accepted

Solution code:
import math

IsPrime = [True] * 100001

IsPrime[0] = False;
IsPrime[1] = False;

for i in range(2, int(math.sqrt(100001)) + 1):
    if IsPrime[i]:
        for j in range(i*i, 100001, i):
            IsPrime[j] = False

cnt = [0] * 100001

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

for i in range(1, 100001):
    cnt[i] += cnt[i-1]

Q = int(raw_input())

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

Submission status: Accepted

Solution code:
def primes(a):
    if a==2 or a%2 != 0:
        return True
    return False

P=[0]*100000

for i in range(2,100000):
    if P[i]==0 and primes(i):
        for j in range(i+i,100000,i):
            P[j] = 1

C=[0]*100000

for i in range(3,100000,2):
    if P[i]==0 and P[int((i+1)/2)]==0:
        C[i]+=1
for i in range(3,100000):
    C[i]+=C[i-1]

N= int(input())

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

for i in range(N):
    print(C[R[i]]-C[L[i]-1])

Submission status: Accepted

Solution code:
def primes(a):
    if a==2 or a%2 != 0:
        return True
    return False

P=[0]*100001

for i in range(2,100001):
    if P[i]==0 and primes(i):
        for j in range(i+i,100001,i):
            P[j] = 1

C=[0]*100002

for i in range(3,100000,2):
    if P[i]==0 and P[int((i+1)/2)]==0:
        C[i]+=1
for i in range(3,100000):
    C[i]+=C[i-1]

N= int(input())

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

for i in range(N):
    print(C[R[i]]-C[L[i]-1])

Submission status: Accepted

Solution code:
import math
Q_SIZE = int(math.pow(10,5))
Q = int(input())

Check_Prime = [True for i in range(Q_SIZE+1)]
Count_like = [0 for i in range(Q_SIZE//2)]

Check_Prime[0] = False
Check_Prime[1] = False

for i in range(2,Q_SIZE+1):
    if(Check_Prime[i] == True):
        for j in range(i+i,Q_SIZE+1,i):
            Check_Prime[j] = False
            
for i in range(1,Q_SIZE//2):
    if(Check_Prime[i*2+1] == True and Check_Prime[int(((i*2+1)+1)/2)] == True):
        Count_like[i] = Count_like[i-1] + 1
    else:
        Count_like[i] = Count_like[i-1]

for i in range(Q):
    l,r = map(int,input().split())
    if( l == 1):
        print(Count_like[r//2] - Count_like[l//2])
    else:
        print(Count_like[r//2] - Count_like[l//2 - 1])

Submission status: Accepted

Solution code:
#abc084d
import math

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

ls=[]
a=0
for i in xrange(10**5):
 if is_prime(i) and is_prime((i+1)/2):
  a+=1
 ls.append(a)
n=int(raw_input())
for i in xrange(n):
 l,r=map(int,raw_input().split())
 print ls[r]-ls[l-1]

Submission status: Accepted

Solution code:
#https://qiita.com/masashi127/items/88436e16e3672b387a58
#--------------------------------------------
import math

def sieve_of_erastosthenes(num):
    input_list = [False if i % 2 == 0 or i % 3 == 0 or i % 5 == 0  else True for i in range(num)]
    input_list[0] = input_list[1] = False
    input_list[2] = input_list[3] = input_list[5] = True
    sqrt = math.sqrt(num)

    for serial in range(3, num, 2):

        if serial >= sqrt:
            return input_list

        for s in range(serial ** 2, num, serial): 
            input_list[s] = False

n=100000
input_list = sieve_of_erastosthenes(n)
prime_list = [i for i, b in enumerate(input_list) if b == True]
#print(prime_list)
#print(sum(prime_list))

#--------------------------------------------

count=[0 for i in range(100002)]
for i in prime_list:
  count[i]=1
#print(count)

nitakazu_count=[0 for i in range(50001)]
for i in range(50001):
  if count[2*i+1]==1 and count[i+1]==1:
    nitakazu_count[i]=1
  
  
ruiseki_count=[0 for i in range(50001)]
for i in range(50000):
  ruiseki_count[i+1]=ruiseki_count[i]+nitakazu_count[i+1]
#print(ruiseki_count)

nn=int(input())

for i in range(nn):
  aa,bb=[int(i) for i in input().split()]
  print(ruiseki_count[int((bb-1)/2)]-ruiseki_count[max(int((aa-1)/2)-1,0)])

Submission status: Accepted

Solution code:
#https://qiita.com/masashi127/items/88436e16e3672b387a58
#--------------------------------------------
import math
def sieve_of_erastosthenes(num):
    input_list = [False if i % 2 == 0 or i % 3 == 0 or i % 5 == 0  else True for i in range(num)]
    input_list[0] = input_list[1] = False
    input_list[2] = input_list[3] = input_list[5] = True
    sqrt = math.sqrt(num)

    for serial in range(3, num, 2):

        if serial >= sqrt:
            return input_list

        for s in range(serial ** 2, num, serial): 
            input_list[s] = False

n=100000
input_list = sieve_of_erastosthenes(n)
prime_list = [i for i, b in enumerate(input_list) if b == True]
#print(prime_list)
#print(sum(prime_list))

#--------------------------------------------

count=[0 for i in range(100002)]
for i in prime_list:
  count[i]=1
#print(count)

nitakazu_count=[0 for i in range(100002)]
for i in range(50001):
  if count[2*i+1]==1 and count[i+1]==1:
    nitakazu_count[2*i+1]=1


dict = {0:0}
ruiseki_count=[0 for i in range(100002)]
for i in range(100000):
#  ruiseki_count[i+1]=ruiseki_count[i]+nitakazu_count[i+1]
  dict [i+1]=dict[i]+nitakazu_count[i+1]

#print(ruiseki_count)

nn=int(input())

for i in range(nn):
  aa,bb=[int(i) for i in input().split()]
#  print(ruiseki_count[bb]-ruiseki_count[aa-1])
  print(dict[bb]-dict[aa-1])