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:
#!/usr/bin/python3
# -*- coding: utf-8 -*-

import sys

isprime = None

def sieve(n):
    global isprime

    if n < 2:
        isprime = [False] * (n + 1)
        return

    isprime = [True if i % 2 != 0 else False for i in range(n + 1)]
    isprime[0] = isprime[1] = False
    isprime[2] = True

    from math import sqrt, ceil

    for i in range(3, int(sqrt(n)) + 1):
        if isprime[i] == True:
            for j in range(i + i, n + 1, i):
                isprime[j] = False

def main():
    global isprime

    sieve(100000)

    _ = sys.stdin.readline()

    csums = [0] * 100001
    for i in range(3, 100001):
        csums[i] += csums[i - 1]
        if isprime[i] == True and isprime[(i + 1) // 2] == True:
            csums[i] += 1

    for l, r in (map(int, line.split()) for line in sys.stdin.readlines()):
        print(csums[r] - csums[l - 1])

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n = int(input())

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

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

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

Submission status: Accepted

Solution code:
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])

Submission status: Accepted

Solution code:
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])

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
# ある自然数未満までのエラトステネスの篩をつくる
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])

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
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 = []
    #print('x={0}'.format(x))
    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)) #  素数のテーブル、inでの判定が速くできるようにリストではなくセットにしておく
    dp = [0] * 100000

    # 1〜99,999までについて、1からのトータルで2017-likeな数字が累計でいくつあるか計算してテーブルにする
    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

    # l 〜 r までで 2017-like数がいくつあるか求める
    for l, r in queries:
        if l == 1:
            ans = dp[r]         #  1からの場合、rまでの数がそのまま答え
        else:
            ans = dp[r] - dp[l-2] #  1〜rまでの数から 1〜l(エル)までの数を引けば、l〜rでの答えになる
        print(ans)


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


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

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
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 = []
    #print('x={0}'.format(x))
    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)) #  素数のテーブル、inでの判定が速くできるようにリストではなくセットにしておく
    dp = [0] * 100000

    # 1〜99,999までについて、1からのトータルで2017-likeな数字が累計でいくつあるか計算してテーブルにする
    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

    # l 〜 r までで 2017-like数がいくつあるか求める
    for l, r in queries:
        if l == 1:
            ans = dp[r]         #  1からの場合、rまでの数がそのまま答え
        else:
            ans = dp[r] - dp[l-2] #  1〜rまでの数から 1〜l(エル)までの数を引けば、l〜rでの答えになる
        print(ans)


def main(args):
    queries = []
    Q = int(input())
    # Q = 0
    # for _ in range(100000):
    #     queries.append((1, 99999))
    queries = [map(int,input().split()) for _ in range(Q)]
    solve(queries)


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

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
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 = []
    #print('x={0}'.format(x))
    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())
    # Q = 0
    # for _ in range(100000):
    #     queries.append((1, 99999))
    for _ in range(Q):
        l, r = map(int, input().split())
        queries.append((l, r))

    solve(queries)


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

Submission status: Accepted

Solution code:
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()

Submission status: Accepted

Solution code:
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])

Submission status: Accepted

Solution code:
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))

Submission status: Accepted

Solution code:
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 i in xrange(0, 54):
  #  print i, ' - ', c[i], primes[i], n_p1_2[i]

  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()

Submission status: Accepted

Solution code:
#coding:UTF-8

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])