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

Solution (Python):
n = int(input())
lr = [None]*100000
rmax = 0
for i in range(n):
    lr[i]= list(map(int,input().split()))
    if lr[i][1] > rmax:
        rmax = lr[i][1]

p = [1]*(rmax+1)
p[0]=0
p[1]=0
        

for j in range(2,int(rmax**0.5+1)):
    if p[j] == 0:
        continue
    for i in range(2,rmax+1):
        if i!=j and i%j == 0:
            p[i] = 0
for i in range(rmax, 1,-2):
    if p[int((i+1)/2)] == 0:
        p[i] = 0
p[2] = 0
for i in range(2,rmax):
    p[i+1] += p[i]  

for i in range(n):
    print(p[lr[i][1]] - p[lr[i][0]-1])

Solution (Python):
import math
n = int(input())
lr = [None]*100000
rmax = 0
for i in range(n):
    lr[i]= list(map(int,input().split()))
    if lr[i][1] > rmax:
        rmax = lr[i][1]

p = [1]*(rmax+1)
p[0]=0
p[1]=0
        

for j in range(2,int(math.sqrt(rmax)+1)):
    if p[j] == 0:
        continue
    for i in range(2,rmax+1):
        if i!=j and i%j == 0:
            p[i] = 0
for i in range(rmax, 1,-2):
    if p[int((i+1)/2)] == 0:
        p[i] = 0
p[2] = 0
for i in range(2,rmax):
    p[i+1] += p[i]  

for i in range(n):
    print(p[lr[i][1]] - p[lr[i][0]-1])

Solution (Python):
prime=[0]*100001
prime[0]=1
prime[1]=1
prime_ans=[0]*100001
for i in range(0,100001):
  if prime[i]==0:
    cnt=2
    while cnt*i<100001:
      prime[cnt*i]=1
      cnt+=1
ans=0
for i in range(3,100001):
  if prime[i]==0 and prime[int((i+1)/2)]==0:
    ans+=1
  prime_ans[i]=ans

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

Solution (Python):

def mark(s, x):
    for i in range(x + x, len(s), x):
        s[i] = False


def eratosthenes(n):
    s = [True] * n
    for x in range(2, int(n ** 0.5) + 1):
        if s[x]: mark(s, x)
    return s

Q = int(input())
LR = [list(map(int, input().split())) for i in range(Q)]

primes = eratosthenes(10 ** 5+1)
primes[0] = False
primes[1] = False

ruiseki = [0] * (10**5 + 1)
for i in range(3, 10**5 + 1, 2):
    if (primes[i]) and (primes[int((i+1)/2)]):
        ruiseki[i] = ruiseki[i-2] + 1
    else:
        ruiseki[i] = ruiseki[i-2]

for l, r in LR:
    print(ruiseki[r] - ruiseki[l-2])

Solution (Python):

"""
https://beta.atcoder.jp/contests/abc084/tasks/abc084_d
AC
"""
import sys
from sys import stdin
from math import ceil, floor
input = stdin.readline


def create_prime_list(limit):
    """ エラトステネスの篩でlimitまでの素数リストを求める
    https://ja.wikipedia.org/wiki/%E3%82%A8%E3%83%A9%E3%83%88%E3%82%B9%E3%83%86%E3%83%8D%E3%82%B9%E3%81%AE%E7%AF%A9
    """
    x = limit**0.5
    primes = []
    
    nums = [x for x in range(2, limit+1)]
    while nums[0]<=x:
        primes.append(nums[0])
        current_prime = nums[0]
        nums = [x for x in nums if x%current_prime != 0]
    primes.extend(nums)
    return primes


def solve(queries):
    primes = set(create_prime_list(10**5)) 
    dp = [0] * 100000

    
    p_num = 0
    for i in range(1, 100000, 2):
        if i in primes and ((i+1)//2) in primes:
            p_num += 1
        dp[i] = p_num

    
    for l, r in queries:
        if l == 1:
            ans = dp[r]         
        else:
            ans = dp[r] - dp[l-2] 
        print(ans)


def main(args):
    queries = []
    Q = int(input())
    
    
    
    for _ in range(Q):
        l, r = map(int, input().split())
        queries.append((l, r))
    solve(queries)


if __name__ == '__main__':
    main(sys.argv[1:])

Solution (Python):

"""
https://beta.atcoder.jp/contests/abc084/tasks/abc084_d
AC
"""
import sys
from sys import stdin
from math import ceil, floor
input = stdin.readline


def create_prime_list(limit):
    """ エラトステネスの篩でlimitまでの素数リストを求める
    https://ja.wikipedia.org/wiki/%E3%82%A8%E3%83%A9%E3%83%88%E3%82%B9%E3%83%86%E3%83%8D%E3%82%B9%E3%81%AE%E7%AF%A9
    """
    x = limit**0.5
    primes = []
    
    nums = [x for x in range(2, limit+1)]
    while nums[0]<=x:
        primes.append(nums[0])
        current_prime = nums[0]
        nums = [x for x in nums if x%current_prime != 0]
    primes.extend(nums)
    return primes


def solve(queries):
    primes = set(create_prime_list(10**5)) 
    dp = [0] * 100000

    
    p_num = 0
    for i in range(1, 100000, 2):
        if i in primes and ((i+1)//2) in primes:
            p_num += 1
        dp[i] = p_num

    
    for l, r in queries:
        if l == 1:
            ans = dp[r]         
        else:
            ans = dp[r] - dp[l-2] 
        print(ans)


def main(args):
    queries = []
    Q = int(input())
    
    
    
    queries = [map(int,input().split()) for _ in range(Q)]
    solve(queries)


if __name__ == '__main__':
    main(sys.argv[1:])

Solution (Python):

"""
https://beta.atcoder.jp/contests/abc084/tasks/abc084_d

"""
import sys
from sys import stdin
from math import ceil, floor
input = stdin.readline


def create_prime_list(limit):
    """ エラトステネスの篩でlimitまでの素数リストを求める
    https://ja.wikipedia.org/wiki/%E3%82%A8%E3%83%A9%E3%83%88%E3%82%B9%E3%83%86%E3%83%8D%E3%82%B9%E3%81%AE%E7%AF%A9
    """
    x = limit**0.5
    primes = []
    
    nums = [x for x in range(2, limit+1)]
    while nums[0]<=x:
        primes.append(nums[0])
        current_prime = nums[0]
        nums = [x for x in nums if x%current_prime != 0]
    primes.extend(nums)
    return primes



def solve(queries):
    primes = set(create_prime_list(10**5))
    dp = [0] * (100000 + 1)

    p_num = 0
    for i in range(1, 100000, 2):
        if i in primes and ((i+1)//2) in primes:
            p_num += 1
        dp[i] = p_num

    for l, r in queries:
        if l == 1:
            ans = dp[r]
        else:
            ans = dp[r] - dp[l-2]
        print(ans)



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

    solve(queries)


if __name__ == '__main__':
    main(sys.argv[1:])

Solution (Python):
def get_prime_array(N):
    f = [0] * (N + 1)
    for i in range(2, N + 1):
        if not f[i]:
            for j in range(i + i, N + 1, i):
                f[j] = 1
    return f


def ans():
    Q = int(input())
    f = get_prime_array(1000001)
    c = [0] * 1000002
    for i in range(3, 1000001, 2):
        if not f[i] and not f[(i + 1) // 2]:
            c[i] += 1

    for i in range(3, 1000000):
        c[i] = c[i] + c[i - 1]

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

ans()

Solution (Python):
MAX_N = 10 ** 5
SQRT_MN = 318
isp = [1] * (MAX_N + 1)
p_list = []
isp[0] = isp[1] = 0
for i in range(2, SQRT_MN + 1):
	if isp[i] == 0:
		continue
	p_list.append(i)
	for prod in range(2, MAX_N // i + 1):
		isp[i * prod] = 0

like_num = [0] * (MAX_N + 1)
for p in range(3, MAX_N + 1):
	if isp[p] and isp[(p + 1) // 2]:
		like_num[p] = 1
	like_num[p] += like_num[p - 1]

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

Solution (Python):
class BIT():
	def __init__(self, N):
		self.bit = [0] * (N + 1)
		self.N = N

	def add(self, a, w):
		x = a
		while x <= self.N:
			self.bit[x] += w
			x += x & (- x)

	def sum(self, a):
		ret = 0
		x = a
		while x > 0:
			ret += self.bit[x]
			x -= x & (- x)
		return ret


MAX_N = 10 ** 5
SQRT_MN = 318
isp = [1] * (MAX_N + 1)
p_list = []
isp[0] = isp[1] = 0
for i in range(2, SQRT_MN + 1):
	if isp[i] == 0:
		continue
	p_list.append(i)
	for prod in range(2, MAX_N // i + 1):
		isp[i * prod] = 0

bit = BIT(MAX_N)
for p in range(3, MAX_N + 1):
	if isp[p] and isp[(p + 1) // 2]:
		bit.add(p, 1)

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

Solution (Python):
from pprint import pprint as pp
def GI(): return int(raw_input())
def GIS(): return map(int, raw_input().split())

from math import sqrt
from itertools import izip

N = 10 ** 5

def main():
  primes = get_primes()
  n_p1_2 = [primes[(i+1)/2] for i in xrange(1, N+1)]
  n_p1_2[2] = 0

  s = 0
  c = []
  for p, n in izip(primes, n_p1_2):
    s += (p and n)
    c.append(s)

  
  

  for _ in xrange(GI()):
    l, r = GIS()
    print c[r] - c[l-1]

def get_primes():
  a = [1] * (N + 1)
  a[0] = a[1] = 0

  for i in xrange(2, int(sqrt(N))):
    if not a[i]:
      continue
    for j in xrange(i ** 2, N+1, i):
      a[j] = 0

  return a

main()

Solution (Python):


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


mx = 10 ** 5
p = [0 for _ in range(mx + 1)]
for i in range(3, mx + 1):
    if i == 2017 or (is_prime(i) and is_prime((i + 1) // 2)):
        p[i] = 1
d = [0 for i in range(mx + 1)]
for i in range(3, mx + 1):
    d[i] += p[i] + d[i - 1]

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