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: Runtime Error

Solution code:
import math
Q = int(input())

def sosuu(x):
  if x == 1:
    return False
  else:
    for i in range(2,int(math.sqrt)):
      if x % i == 0:
        return False
    return True

table=[0]*50000
for i in range(1,50001):
  if sosuu(2*i - 1) and sosuu(i):
    table[i]=table[i-1] + 1
  else:
    table[i]=table[i-1]
    
ans=[0]*Q
for i in range(Q):
  l,r=map(int,input().split())
  ans[i]=table[(r+1)//2] - table[(l+1)//2]
for i in range(Q):
  print(ans[i])

Submission status: Runtime Error

Solution code:
from sys import stdin
def main():
  from math import sqrt
  readline = stdin.readline
  p = [True] * (10 ** 5 + 1)
  p[0] = False
  p[1] = False
  n = int(sqrt(10 ** 5 + 1)) + 1
  for j in range(4, n, 2):
    p[j] = False
  for i in range(3, n, 2):
    if p[i]:
      for j in range(i + i, n, i):
        p[j] = False
  c = [0] * (10 ** 5 + 1)
  for i in range(2, 10 ** 5 + 1):
    c[i] = c[i - 1]
    if p[i - 2] and p[(i - 1) // 2]:
      c[i] += 1
  q = int(readline())
  for _ in range(q):
    l, r = map(int, readline().split())
    print(c[r + 2] - c[l + 1])
main()

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline

n=10**5
sievebd=n//2-1
sieve=[True]*sievebd
limit=(int((n-1)**.5)-1)//2
for i in range(limit):
    if sieve[i]:
        for j in range(2*i**2+6*i+3,sievebd,2*i+3):
            sieve[j]=False
for i in range((sievebd-1)//2-1,-1,-1):
    if not sieve[i]:sieve[2*i+1]=False
for i in range(2,sievebd,2):
    sieve[i]=False

sieve[0]=1
for i in range(1,sievebd):
    sieve[i]+=sieve[i-1]

q=int(input())
l=[0]*q
r=[0]*q
for i in range(q):
    l[i],r[i]=map(int,input().split())

for i in range(q):
    print(sieve[max(1,(r[i]-3)//2+1)]-sieve[max(0,(l[i]-3)//2)])

Submission status: Runtime Error

Solution code:
import math
Q = int(input())

def prime(p):
    for i in range(2, int(math.sqrt(p))+1):
        if p % i == 0:
            return False
    return True

# エラトステネスの篩
data = [1]*10**5
data[0], data[1] = 0, 0
for j in range(2, len(data)):
    if prime(j) == True:
        for k in range(j*2, len(data), j):
            data[k] = 0


# 2017 like
for e in range(2, len(data))[::-1]:
    if data[e] == 1 and (e) % 2 == 1:
        if data[int((e+1)/2)] == 0:
            data[e] = 0
    else:
        data[e] = 0
# 累積和
t = [0]*len(data)
for a in range(len(data)-1):
    t[a+1] = t[a] + data[a]

for b in range(Q):
    l, r = map(int, input().split(" "))
    print(t[r+1] - t[l])

Submission status: Runtime Error

Solution code:
import math
Q = int(input())

def prime(p):
    for i in range(2, int(math.sqrt(p))+1):
        if p % i == 0:
            return False
    return True

# エラトステネスの篩
data = [1]*(10**5+1)
data[0],data[1] = 0,0 #
for j in range(2, 10**5+1):
    if prime(j) == True:
        for k in range(j*2, 10**5+1, j):
            data[k] = 0
# 2017 like
for k in range(2,10**5)[::-1]: #
    if data[k] == 1 and k % 2 == 1:
        if data[int((k+1)/2)] == 0:
            data[k] = 0
    else: #
        data[k] = 0 #
# 累積和
t = [0]*10**5
for a in range(10**5-1):
    t[a+1] = t[a] + data[a]

for b in range(Q):
    l, r = map(int, input().split(" "))
    print(t[r+1] - t[l])

Submission status: Runtime Error

Solution code:
import math
Q = int(input())

def prime(p):
    for i in range(2, int(math.sqrt(p))+1):
        if p % i == 0:
            return False
    return True

# エラトステネスの篩
data = [1]*10**5
data[0],data[1] = 0,0 #
for j in range(2, 10**5):
    if prime(j) == True:
        for k in range(j*2, 10**5, j):
            data[k] = 0
# 2017 like
for k in range(2,10**5)[::-1]: #
    if data[k] == 1 and k % 2 == 1:
        if data[int((k+1)/2)] == 0:
            data[k] = 0
    else: #
        data[k] = 0 #
# 累積和
t = [0]*10**5
for a in range(10**5-1):
    t[a+1] = t[a] + data[a]

for b in range(Q):
    l, r = map(int, input().split(" "))
    print(t[r+1] - t[l])

Submission status: Runtime Error

Solution code:
import math 

def prime(n):
    for k in range(2, int(math.sqrt(n)) + 1):
        if n % k == 0:
            return 0
    return 1

#エラトステネスのふるい
MAX =100000
is_prime = [1]*(MAX+1)
is_prime[0],is_prime[1] == 0
for i in range(2,MAX+1):
    if prime(i) == 1:
        j = i*2
        while j <= MAX:
            is_prime[j] = 0
            j += i

#２０１７のような数かどうか
a = [0]*(MAX+1)
for i in range(0,MAX):
    if i % 2 == 1:
        if is_prime[i]==1 and is_prime[int((i+1)/2)]==1:
            a[i] = 1

#累積和
s = [0] * (MAX+1)
for i in range(0,MAX):
    s[i+1] = s[i] + a[i]

#クエリ処理
Q = input()
for q in range(Q):
    l,r = map(int,input().split())
    r += 1

    print(s[r]-s[l])

Submission status: Runtime Error

Solution code:
def prime(i):
    if i == 1:
        return False
    if (i > 2) & (i % 2 == 0):
        return False
    for j in range(3, int(i**(0.5)) + 1, 2):
        if i % j == 0:
            return False
    return True



q = int(input())
for _ in range(q):
    ans = 0
    l, r = map(int, input().split())
    while (i <= r):
        if prime(i) & prime(int(i+1)//2):
            ans += 1
            i += 4
        else:
            i += 2
    print(ans)

Submission status: Runtime Error

Solution code:
def prime(n):
    is_prime = [True] * (n + 1)
    is_prime[0] = False
    is_prime[1] = False
    for j in range(4, n+1, 2):
        is_prime[j] = False
    for i in range(3, int(n**0.5) + 1, 2):
        if not is_prime[i]:
            continue
        for j in range(i * 2, n + 1, i):
            is_prime[j] = False
    return [i for i in range(n + 1) if is_prime[i]]

Q = int(input())
l, r = [0]*Q, [0]*Q
for i in range(Q):
    l[i], r[i] = map(int, input().split())
 
K = max(r)
prime = Eratosthenes(K)
ans = [0]
for i in range(K):
    if i % 2 == 0:
        ans.append(ans[-1])
    elif i in prime and (i+1)/2 in prime:
        ans.append(ans[-1]+1)
    else:
        ans.append(ans[-1])
        
for j in range(Q):
    if r[j] == l[j]:
        print(0)
    else:
        print(ans[r[j]]-ans[l[j]])

Submission status: Runtime Error

Solution code:
#include <cstring>
#include <iostream>
#include <vector>

using namespace std;

class Prime {
// n以下の素数を列挙する
public:
  const int n;
  vector<bool> is_prime;
  vector<int> primes;
  Prime(int size) : n(size), is_prime(n, true) {
    is_prime[0] = false;
    is_prime[1] = false;
    for (int i = 2; i <= n; ++i) {
      if (!is_prime[i]) continue;
      primes.push_back(i);
      int tmp = 2*i;
      while (tmp <= n) {
        is_prime[tmp] = false;
        tmp += i;
      }
    }
  }

  bool check(int x) { return is_prime[x]; }
};

int dp[100001];

int main() {
  memset(dp, 0, sizeof(dp));
  Prime prime(100001);
  for (int i = 1; i <= 100000; ++i) {
    dp[i] = dp[i-1];
    if (i % 2 == 0) continue;
    if (!prime.check(i)) continue;
    if (!prime.check((i+1)/2)) continue;
    dp[i] += 1;
  }

  int q;
  cin >> q;
  for (int i = 0; i < q; ++i) {
    int l, r;
    cin >> l >> r;
    cout << dp[r] - dp[l-1] << endl;
  }
}

Submission status: Runtime Error

Solution code:
import numpy as np

q = int(input())

# 高速素数判定
is_prime = np.ones(100001, dtype=int)
is_prime[0]=0
is_prime[1]=0

for i in range(2,100001):
    if is_prime[i]==1:
        j=i+i
        while j <= 100000:
            is_prime[j] = 0
            j += i

like2017 = [1 if is_prime[x] and is_prime[(x+1)//2] else 0 for i in range(0,100001) ]

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

Submission status: Runtime Error

Solution code:
import numpy as np
n=10000
q = int(input())
 
is_prime = np.ones(n+1,dtype=int)
is_prime[0]=0
is_prime[1]=0
 
for i in range(2,n+1):
    if(is_prime[i]==1):
        j=i+i
        while j <= n:
            is_prime[j] = 0
            j += i
 
cnt = [is_prime[x]*is_prime[(x+1)//2] for x in range(0,n+1)]
 
for i in range(1,n+1):
    cnt[i]+=cnt[i-1]
 
for i in range(q):
    l,r = map(int, input().split())
    print(cnt[r]-cnt[l-1])

Submission status: Runtime Error

Solution code:
import numpy as np
 
q = int(input())
 
# 高速素数判定
is_prime = np.ones(10001, dtype=int)
is_prime[0]=0
is_prime[1]=0
 
for i in range(2,10001):
    if is_prime[i]==1:
        j=i+i
        while j <= 10000:
            is_prime[j] = 0
            j += i
            
like2017 = [is_prime[x]*is_prime[(x+1)//2] for x in range(0,10001)]
 
for i in range(1,10001):
    like2017[i] += like2017[i-1]
    
for i in range(q):
    l,r = map(int, input().split())
    print(like2017[r]-like2017[l-1])

Submission status: Runtime Error

Solution code:
import numpy as np
 
q = int(input())
 
# 高速素数判定
is_prime = np.ones(10001, dtype=int)
is_prime[0]=0
is_prime[1]=0
 
for i in range(2,10001):
    if is_prime[i]==1:
        j=i+i
        while j <= n:
            is_prime[j] = 0
            j += i
            
like2017 = [is_prime[x]*is_prime[(x+1)//2] for x in range(0,10001)]
 
for i in range(1,10001):
    like2017[i] += like2017[i-1]
    
for i in range(q):
    l,r = map(int, input().split())
    print(like2017[r]-like2017[l-1])

Submission status: Runtime Error

Solution code:
import numpy as np

q = int(input())

# 高速素数判定
is_prime = np.ones(10001, dtype=int)
is_prime[0]=0
is_prime[1]=0

for i in range(2,10001):
    if is_prime[i]==1:
        j=i+i
        while j <= n:
            is_prime[j] = 0
            j += i
            
like2017 = [is_prime[x]*is_prime[(x+1)//2] for x in range(0,10001)]

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

Submission status: Runtime Error

Solution code:
q = int(input())
l = []
r = []
for i in range(q):
    li, ri = map(int, input().split())
    l.append(li)
    r.append(ri)

r_max = max(r) + 10
is_prime = [True] * r_max
is_prime[0] = False
is_prime[1] = False
for i in range(2, r_max):
    if is_prime[i]:
        for j in range(2, r_max // i + 1):
            is_prime[i*j] = False

# print(is_prime)
a = [0] * r_max
for i in range(3, r_max):
    a[i] = a[i-1]
    if is_prime[i] and is_prime[(i+1)//2]:
        a[i] += 1
# print(a)

for i in range(q):
    print(a[r[i]] - a[l[i]-1])

Submission status: Runtime Error

Solution code:
q = int(input())
l = []
r = []
for i in range(q):
    li, ri = map(int, input().split())
    l.append(li)
    r.append(ri)

r_max = max(r) + 10
is_prime = [True] * r_max
is_prime[0] = is_prime[1] = False
for i in range(2, r_max):
    if is_prime[i]:
        for j in range(2, r_max // i + 1):
            is_prime[i*j] = False

# print(is_prime)
a = [0] * r_max
for i in range(3, r_max):
    a[i] = a[i-1]
    if is_prime[i] and is_prime[(i+1)//2]:
        a[i] += 1
# print(a)

for i in range(q):
    print(a[r[i]] - a[l[i]-1])

Submission status: Runtime Error

Solution code:
#include"bits/stdc++.h"
#define int long long
#define _overload3(_1,_2,_3,name,...) name
#define _rep(i,n) repi(i,0,n)
#define repi(i,a,b) for(int i=(a);i<(b);++i)
#define rep(...) _overload3(__VA_ARGS__,repi,_rep,)(__VA_ARGS__)
#define itr(i,x) for(auto i=(x).begin();i!=(x).end();++i)
#define All(x) (x).begin(),(x).end()
#define gridif(a,x,b) if((a)<=(x)&&(x)<(b))

using namespace std;
typedef pair<int,int> P;
const int mod=1000000007;

int digitsum(int n,int b){
	if(b<2) return -1;
	if(n<b) return n;
	return digitsum(n/b,b)+n%b;
}
int mpow(int a,int x){
	int ans=1;
	while(x>0){
		if(x%2==1) (ans*=a)%=mod;
		(a*=a)%=mod;
		x>>=1;
	}
	return ans;
}
int m_inv(int n){return mpow(n,mod-2);}
vector<int> split(string s,int a){
	if(a<0||a>s.length()) return {-1,-1};
	string l="0",r="0";
	if(a!=0) l=s.substr(0,a);
	if(a!=s.length()) r=s.substr(a);
	return{stoll(l),stoll(r)};
}
string xal_number(int n,int x){
	if(x>36) return "out of use";
	if(n==0) return "";
	string s;
	int i=n%x;
	char a = i + ( i >= 10 ? 'A'-10 : '0' );
	s=xal_number(n/x,x)+a;
	return s;
}
int gcd(int x,int y){return y?gcd(y,x%y):x;}
int lcm(int x,int y){return x*y/gcd(x,y);}
class Factorial{
private:
	vector<int> fac;
public:
	Factorial(int N){
		fac.push_back(1);
		rep(i,N) fac.push_back(fac[i]*(i+1)%mod);
	}
	int fact(int a){return fac[a];}
	int ifac(int a){return m_inv(fac[a]);}
	int cmb(int n,int r){
		if(n<r) return 0;
		if(r==0||r==n) return 1;
		return fac[n]*ifac(r)%mod*ifac(n-r)%mod;
	}
};
struct UnionFind {
    vector<int> par; // 親ノード
    UnionFind(int n = 1) { init(n);}
    void init(int n = 1) {
        par.resize(n);
        rep(i,n) par[i] = -1;
    }
    int root(int x) {
        if (par[x] <0) return x;
        else return par[x] = root(par[x]);      
    }
    int size(int x){ return -par[root(x)];}
    bool issame(int x, int y) {return root(x)==root(y);}
    bool connect(int x,int y) {
        x = root(x); y = root(y);
        if (x == y) return false;
        if (size(x) < size(y)) swap(x, y);
        par[x] += par[y];
        par[y] = x;
        return true;
	}
};
struct edge{int from;int to;int cost;};
template<int N> class Graph{
private:
	int inf=1LL<<40;
	vector<edge> e;
	vector<vector<int>> dist;
public:
	Graph(){
		dist.resize(N,vector<int>(N));
		rep(i,N) rep(j,N) dist[i][j]=(i==j)?0:inf;
	}
	Graph(const Graph &cp){dist=cp.dist;e=cp.e;}
	void push(int a,int b,int c){
		e.emplace_back();
		e.back().from=a;e.back().to=b;e.back().cost=c;
	}
	void reverse(){
		rep(i,e.size()) swap(e[i].from,e[i].to);
	}
	int distance(int a,int b){return dist[a][b];}
	void load(int M){
		e.resize(M);
		rep(i,M){
			int a,b;
			cin>>a>>b;a--;b--;
			e[i].from=a;e[i].to=b;e[i].cost=1;
		}
	}
	void wload(int M){
		e.resize(M);
		rep(i,M){
			int a,b,c;
			cin>>a>>b>>c;a--;b--;
			e[i].from=a;e[i].to=b;e[i].cost=c;
		}
	}
	void undirect(){
		int m=e.size();
		e.resize(2*m);
		rep(i,m){
			e[i+m].from=e[i].to;
			e[i+m].to=e[i].from;
			e[i+m].cost=e[i].cost;
		}
	}
	void out(){
		rep(i,e.size()) cout<<e[i].from+1<<" "<<e[i].to+1<<endl;
	}
	void bfs(int s){
		vector<vector<P>> graph(N);
		rep(i,e.size()) graph[e[i].from].push_back(P(e[i].cost,e[i].to));
		queue<int> que;
		que.push(s);
		while(!que.empty()){
			int u=que.front();que.pop();
			rep(i,graph[u].size()){
				int v=graph[u][i].second;
				if(dist[s][v]!=inf) continue;
				que.push(v);dist[s][v]=dist[s][u]+graph[u][i].first;
			}
		}
	}
	void dijkstra(int s){
		vector<vector<P>> graph(N);
		rep(i,e.size()) graph[e[i].from].push_back(P(e[i].cost,e[i].to));
		priority_queue<P,vector<P>,greater<>> que;
		que.push(P(s,0));
		while(!que.empty()){
			P p=que.top();que.pop();
			int u=p.first;
			if(dist[s][u]<p.second) continue;
			rep(i,graph[u].size()){
				int v=graph[u][i].second;
				int alt=dist[s][u]+graph[u][i].first;
				if(dist[s][v]>alt){
					dist[s][v]=alt;
					que.push(P(v,alt));
				}
			}
		}
	}
	void shortest_path(){
		rep(i,e.size()) dist[e[i].from][e[i].to]=e[i].cost;
		rep(k,N) rep(i,N) rep(j,N){
			dist[i][j]=min(dist[i][j],dist[i][k]+dist[k][j]);
		}
	}
	void bellman(int s){
		rep(i,N-1) rep(j,e.size()){
			dist[s][e[j].to]=min(dist[s][e[j].from]+e[j].cost,dist[s][e[j].to]);
		}
	}
	bool nloop(int s,int t){
		bellman(s);
		vector<bool> negative(N,false);
		rep(i,N) rep(j,e.size()){
			if(dist[s][e[j].to]>dist[s][e[j].from]+e[j].cost){
				dist[s][e[j].to]=dist[s][e[j].from]+e[j].cost;
				negative[e[j].to]=true;
			}
			if(negative[e[j].from]) negative[e[j].to]=true;
		}
		if(negative[t]) return true;
		else return false;
	}
	int prim(){
		vector<vector<P>> graph(N);
		rep(i,e.size()) graph[e[i].from].push_back(P(e[i].cost,e[i].to));
		vector<bool> used(N,false);
		priority_queue<P,vector<P>,greater<>> que;
		que.push(P(0,0));
		int ret=0;
		while(!que.empty()){
			P p=que.top();que.pop();
			int u=p.second;
			if(used[u]) continue;
			used[u]=true;
			ret+=p.first;
			rep(i,graph[u].size()) que.push(P(graph[u][i].first,graph[u][i].second));
		}
		return ret;
	}
	Graph<N> kruskal(){
		Graph<N> G;
		sort(All(e),[](const edge &x,const edge &y){return x.cost<y.cost;});
		UnionFind uni(N);
		rep(i,e.size()){
			if(uni.connect(e[i].from,e[i].to)){
				G.push(e[i].from,e[i].to,e[i].cost);
			}
		}
		return G;
	}
};
class Sosu{
 private:
    vector<int> Prime_Number;
 public:
    Sosu(int N){
        set<int> arr;
        rep(i,N-1)  arr.insert(i+2);
        while(int n=*arr.begin()){
            if(n>sqrt(N)) break;
            Prime_Number.push_back(n);
            rep(i,1,N/n+1) arr.erase(n*i);
        }
        itr(it,arr) Prime_Number.push_back(*it);
    }
    int operator[](int i){return Prime_Number[i];}
    int count(){return Prime_Number.size();}
    bool isPrime(int q){return binary_search(All(Prime_Number),q);}
};
signed main(){
	int q;
	cin>>q;
	Sosu p(100001);
	int S[100001];
	rep(i,1,100001){ 
		if(i&1){ 
			if(p.isPrime(i)&&p.isPrime((i+1)/2)){
				S[i]=S[i-1]+1;
			}
		}
		S[i]=max(S[i],S[i-1]);
	}
	rep(i,q){
		int l,r;
		cin>>l>>r;
		cout<<S[r]-S[l-1]<<endl;
	}
}

Submission status: Runtime Error

Solution code:
max_num = 10**5+5
eratos_thenes_sieve = [0,0] + [1]*maxnum
n = 2 #素数
while n*n <= max_num:
  if eratos_thenes_sieve[n]:#
    for i in range(2*n, max_num, n):
      eratos_thenes_sieve[i] = 0
  n += 1
  
isLike2017 = [0] * max_num
cumulativeSums = [0]
for i in range(max_num):
  if eratos_thenes_sieve[i] and eratos_thenes_sieve[(i+1)//2]:
    isLike2017[i] = 1
  cumulativeSums.append(cumulativeSums[-1] + isLike2017[i])
  
  
q = int(input())

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

Submission status: Runtime Error

Solution code:
finished = [False] * 10**5
isPN = [False] * 10**5
def isPrimeNumber(num):
  if finished[num]:
    return isPN[num]
  
  if num == 1:
    return False
  pn = 2
  while pn * pn <= num:
    if num % pn == 0:
      finished[num] = True
      isPN[num] = False
      return isPN[num]
    pn += 1
  
  
  finished[num] = True
  isPN[num] = True
  return isPN[num]

n = int(input())

l = [0] * n
r = [0] * n
for i in range(n):
  l[i], r[i] = map(int, input().split())
  
  
for i in range(n):
  ans = 0
  for j in range(l[i], r[i]+1, 2):
    if isPrimeNumber(j) and isPrimeNumber((j+1)/2):
      ans += 1
      
  print(ans)

Submission status: Runtime Error

Solution code:
Q=int(input())
n=100
is_prime=[1]*(n+10)
is_prime[0]=0
is_prime[1]=0
for i in range(2,n+1):
	for j in range(i*2,n+1,i):
		if is_prime[j]==False:
			continue
		is_prime[j]=0
a=[0]*(n+10)
for j in range(2,n+1):
	if is_prime[j]%2==0:
		continue
	if is_prime[j] and is_prime[int((j+1)/2)]:
		a[j]=1
s=[0]*(n+10)		
for k in range(n):
	s[k+1]=a[k]+s[k]
ans=[]
for _ in range(Q):
	l,r=map(int,input().split())
	ans.append(s[r+1]-s[l])
print(*ans,sep='\n')

Submission status: Runtime Error

Solution code:
Q=int(input())
n=100
is_prime=[1]*(n+10)
is_prime[0]=0
is_prime[1]=0
for i in range(2,n+1):
	for j in range(i*2,n+1,i):
		if is_prime[j]==False:
			continue
		is_prime[j]=0
a=[0]*(n+10)
for i in range(2,n+1):
	if is_prime[i]%2==0:
		continue
	if is_prime[i] and is_prime[int((i+1)/2)]:
		a[i]=1
s=[0]*(n+10)		
for i in range(n):
	s[i+1]=a[i]+s[i]
ans=[]
for i in range(Q):
	l,r=map(int,input().split())
	ans.append(s[r+1]-s[l])
print(*ans,sep='\n')

Submission status: Runtime Error

Solution code:
Q=int(input())
n=10100
is_prime=[1]*(n+10)
is_prime[0]=0
is_prime[1]=0
for i in range(2,n+1):
	for j in range(i*2,n+1,i):
		if is_prime[j]==False:
			continue
		is_prime[j]=0
a=[0]*(n+10)
for i in range(2,n+1):
	if is_prime[i]%2==0:
		continue
	if is_prime[i] and is_prime[int((i+1)/2)]:
		a[i]=1
s=[0]*(n+10)		
for i in range(n):
	s[i+1]=a[i]+s[i]
ans=[]
for i in range(Q):
	l,r=map(int,input().split())
	ans.append(s[r+1]-s[l])
print(*ans,sep='\n')

Submission status: Runtime Error

Solution code:
Q=int(input())
n=10100
is_prime=[1]*(n+10)
is_prime[0]=0
is_prime[1]=0
for i in range(2,n+1):
	for j in range(i*2,n+1,i):
		if is_prime[j]==False:
			continue
		is_prime[j]=0
a=[0]*(n+10)
for i in range(2,n+1):
	if is_prime[i]%2==0:
		continue
	if is_prime[i] and is_prime[int((i+1)/2)]:
		a[i]=1
s=[0]*(n+10)		
for i in range(n):
	s[i+1]=a[i]+s[i]
for i in range(Q):
	l,r=map(int,input().split())
	print(s[r+1]-s[l])

Submission status: Runtime Error

Solution code:
Q=int(input())
n=10010
is_prime=[1]*(n+1)
is_prime[0]=0
is_prime[1]=0
for i in range(2,n+1):
	for j in range(i*2,n+1,i):
		if is_prime[j]==False:
			continue
		is_prime[j]=0
a=[0]*(n+1)
for i in range(2,n+1):
	if is_prime[i]%2==0:
		continue
	if is_prime[i] and is_prime[int((i+1)/2)]:
		a[i]=1
s=[0]*(n+1)		
for i in range(n):
	s[i+1]=a[i]+s[i]
for i in range(Q):
	l,r=map(int,input().split())
	print(s[r+1]-s[l])

Submission status: Runtime Error

Solution code:
Q=int(input())
n=10010
is_prime=[1]*(n+1)
is_prime[0]=is_prime[1]=0
for i in range(2,n+1):
	for j in range(i*2,n+1,i):
		if is_prime[j]==False:
			continue
		is_prime[j]=0
a=[0]*(n+1)
for i in range(2,n+1):
	if is_prime[i]%2==0:
		continue
	if is_prime[i] and is_prime[int((i+1)/2)]:
		a[i]=1
s=[0]*(n+1)		
for i in range(n):
	s[i+1]=a[i]+s[i]
for i in range(Q):
	l,r=map(int,input().split())
	print(s[r+1]-s[l])

Submission status: Runtime Error

Solution code:
Q=int(input())
n=10010
is_prime=[1]*(n+1)
is_prime[0]=is_prime[1]=0
for i in range(2,n+1):
	for j in range(i*2,n+1,i):
		if is_prime[j]==False:
			continue
		is_prime[j]=0
a=[0]*(n+1)
for i in range(n+1):
	if is_prime[i]%2==0:
		continue
	if is_prime[i] and is_prime[int((i+1)/2)]:
		a[i]=1
s=[0]*(n+1)		
for i in range(n):
	s[i+1]=a[i]+s[i]
for i in range(Q):
	l,r=map(int,input().split())
	print(s[r+1]-s[l])

Submission status: Runtime Error

Solution code:
Q=int(input())
n=10010
is_prime=[1]*(n+1)
is_prime[0]=is_prime[1]=0
for i in range(2,int(n**0.5)*1):
	for j in range(i*2,n+1,i):
		if is_prime[j]==False:
			continue
		is_prime[j]=0
a=[0]*(n+1)
for i in range(n+1):
	if is_prime[i]%2==0:
		continue
	if is_prime[i] and is_prime[int((i+1)/2)]:
		a[i]=1
s=[0]*(n+1)		
for i in range(n):
	s[i+1]=a[i]+s[i]
for i in range(Q):
	l,r=map(int,input().split())
	print(s[r+1]-s[l])

Submission status: Runtime Error

Solution code:
def sieve(n): # エラトステネスの篩
    num = [1]*n
    num[0]=num[1]= 0
    for i in range(int(n**0.5)+1):
        if num[i]:
            for j in range(i**2,n,i):
                num[j] = 0
    return num # list ### 1なら素数0なら合成数

primes = sieve(10**5)
like_2017 = [0]
for i in range(1,len(primes)):
    if i <= 2:
        like_2017.append(like_2017[i-1])
    elif primes[i] == 1 and primes[(i+1)//2] == 1:
        like_2017.append(like_2017[i-1]+1)
    else:
        like_2017.append(like_2017[i-1])
Q = int(input())
for q in range(Q):
    l,r = map(int,input().split())
    print(like_2017[r+1]-like_2017[l-1])

Submission status: Runtime Error

Solution code:
def sieve_of_eratosthenes(n):
    pl = [i for i in range(2, n + 1)]
    i=0
    p = pl[0]
    while p**2<=n:
        pl = [pl[j] for j in range(len(pl)) if pl[j]%p!=0 or j<=i]
        i+=1
        p=pl[i]
    return pl

pl=sieve_of_eratosthenes(100000)

p_list = [0 for i in range(100001)]

for p in pl:
    if 2*p-1<=100000:
        p_list[2*p-1]+=1
    p_list[p]+=1


ps_list = [0]
ps = 0

for i in range(1,100001):
    if p_list[i]>=2:
        ps+=1
        ps_list.append(ps)



Q = int(input())

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

Submission status: Runtime Error

Solution code:
def sieve_of_eratosthenes(n):
    pl = [i for i in range(2, n + 1)]
    i=0
    p = pl[0]
    while p**2<=n:
        pl = [pl[j] for j in range(len(pl)) if pl[j]%p!=0 or j<=i]
        i+=1
        p=pl[i]
    return pl

pl=sieve_of_eratosthenes(100000)

p_list = [0 for i in range(100001)]

for p in pl:
    p_list[2*p-1]+=1
    p_list[p]+=1


ps_list = [0]
ps = 0

for i in range(1,100001):
    if p_list[i]>=2:
        ps+=1
        ps_list.append(ps)



Q = int(input())

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

Submission status: Runtime Error

Solution code:
import math
import copy
from collections import defaultdict
from collections import Counter
from collections import deque
# 直積 A={a, b, c}, B={d, e}:のとき，A×B={(a,d),(a,e),(b,d),(b,e),(c,d),(c,e)}: product(A, B)
from itertools import product
# 階乗 P!: permutations(seq), 順列 {}_len(seq) P_n: permutations(seq, n)
from itertools import permutations
# 組み合わせ {}_len(seq) C_n: combinations(seq, n)
from itertools import combinations
from bisect import bisect_left, bisect_right
# import numpy as np

def inside(y, x, H, W):
    return 0 <= y < H and 0 <= x < W

# 四方向: 右, 下, 左, 上
dy = [0, -1, 0, 1]
dx = [1, 0, -1, 0]

def i_inpl(): return int(input())
def s_inpl(): return map(int,input().split())
def l_inpl(): return list(map(int, input().split()))
INF = float("inf")
MAX_DIGIT = 50

############
############
############

Q = i_inpl()
l, r = [], []

max_r = -INF
for _ in range(Q):
    li, ri = l_inpl()
    l.append(li)
    r.append(ri)
    max_r = max(max_r, ri)

MAX_X = 100000
prime_table = [True] * MAX_X
prime_table[0] = prime_table[1] = False

for (i, is_prime) in enumerate(prime_table):
    if is_prime:
        for n in range(i*i, MAX_X, i):
            prime_table[n] = False

# 1は2017に似てない数字
cumsums = [0]
for odd in range(3, max_r+3, 2):
    tmp = 0
    if prime_table[odd] and prime_table[(odd+1)//2]:
        tmp += 1
    cumsums.append(cumsums[-1] + tmp)

for li, ri in zip(l, r):
    if li > 1:
        li = li//2 - 1
    else:
        li = 0
    ri = ri//2
    print(cumsums[ri]-cumsums[li])

Submission status: Runtime Error

Solution code:
def prime(n):
  if n==1:
    return False
  elif n==2 or n==3:
    return True
  else:
    for i in range(2,int(n**0.5)+1):
      if n%i==0:
        return False
    else:
      return True

ans=[0]*(10**5+1)
for i in range(3,10**5+1,2):
  if prime(i) and prime((i+1)//2):
    ans[i]=1
for i in range(1,10**5+1)=:
  ans[i]=ans[i]+ans[i-1]
q=int(input())
for i in range(q):
  l,r=map(int,input().split())
  print(ans[r]-ans[l-1])

Submission status: Runtime Error

Solution code:
import math
def primes(n):
    a = list(range(2, n+1))
    primes = [2]
    for i in a:
        flag = True
        m = math.sqrt(i)
        for j in primes:
            if j > m:
                break
            else:
                if i % j == 0:
                    flag = False
                    break
        if flag:
            primes.append(i)
    return primes
primes = primes(10**5)
dp = [0]*(10**5+1)
cnt = 0
for i in range(1, 10**5+1, 2):
    if i in primes:
        if (i+1)//2 in primes:
            cnt += 1
    dp[i] = cnt
 
    
Q = int(input())
for _ in range(Q):
    l, r = map(int, input().split())
    print(dp[r]-dp[l-2])
import math
def primes(n):
    a = list(range(2, n+1))
    primes = [2]
    for i in a:
        flag = True
        m = math.sqrt(i)
        for j in primes:
            if j > m:
                break
            else:
                if i % j == 0:
                    flag = False
                    break
        if flag:
            primes.append(i)
    return primes
primes = primes(10**5)
dp = [0]*(10**5+1)
cnt = 0
for i in range(1, 10**5+1, 2):
    if i in primes:
        if (i+1)//2 in primes:
            cnt += 1
    dp[i] = cnt

    
Q = int(input())
for _ in range(Q):
    l, r = map(int, input().split())
    print(dp[r]-dp[l-2])
提出情報

Submission status: Runtime Error

Solution code:
q = int(input())
l = [list(map(int,input().split())) for _ in range(q)]

def prime_table(n):
    list = [True for _ in range(n+1)]
    for i in range(2,int(n**0.5)+1):
        if list[i]:
            j = i*2
            while j<=n:
                list[j] = False
                j += i
    table = [i for i in range(n+1) if list[i] and i>=2]
    return table

table = prime_table(10**5)
table = set(table)
sim_sum = [0]*(10**5+1)

for i in range(len(table)):
    if table[i]*2-1 in table:
        sim_sum[table[i]*2-1] += 1
for i in range(1,10**5+1):
    sim_sum[i] += sim_sum[i-1]
for l_ in l:
    print(sim_sum[l_[1]]-sim_sum[max(l_[0]-2,0)])

Submission status: Runtime Error

Solution code:
import sys
import bisect
import math
input = sys.stdin.readline

n = int(input())
l = [list(map(int, input().split())) for _ in range(n)]

mc = max(l)[1]
mc_sqrt = math.sqrt(mc)

prime = [i for i in range(2, mc + 1)]
c = 0
while True:
    if c >= len(prime):
        break
    t = prime[c]
    prime = [v for v in prime if v == t or v % t != 0]
    c = c + 1
    if c >= mc_sqrt:
        break
        
cum = [0 for i in range(mc + 1)]
for i in range(len(cum)):
    prime_index = bisect.bisect_left(prime, i)
    
    n2 = (i + 1) / 2
    prime_index2 = bisect.bisect_left(prime, n2)
    if len(prime) > prime_index and len(prime) > prime_index2 and prime[prime_index] == i and prime[prime_index2] == n2:
        cum[i] = cum[i - 1] + 1
    else:
        if i - 1 < 0:
            cum[i] = 0
        else:
            cum[i] = cum[i - 1]

for t in l:
    x, y = t[0], t[1]
    p = 0
    if 0 <= x - 1:
        p = cum[x] - cum[x - 1]
    if x != y:
        p = p + cum[y] - cum[x]
    print(p)

Submission status: Runtime Error

Solution code:
import sys
import bisect
import math
input = sys.stdin.readline

n = int(input())
l = [list(map(int, input().split())) for _ in range(n)]

mc = max(l)[1]
mc_sqrt = math.sqrt(mc)

prime = [i for i in range(2, mc + 1)]
c = 0
while True:
    if c >= len(prime):
        break
    t = prime[c]
    prime = [v for v in prime if v == t or v % t != 0]
    c = c + 1
    if c >= mc_sqrt:
        break
        
cum = [0 for i in range(mc + 1)]
for i in range(len(cum)):
    prime_index = bisect.bisect_left(prime, i)
    
    n2 = (i + 1) / 2
    prime_index2 = bisect.bisect_left(prime, n2)
    if len(prime) > prime_index and len(prime) > prime_index2 and prime[prime_index] == i and prime[prime_index2] == n2:
        cum[i] = cum[i - 1] + 1
    else:
        if i - 1 < 0:
            cum[i] = 0
        else:
            cum[i] = cum[i - 1]

for t in l:
    if len(t) != 2:
        sys.exit()
    x, y = t[0], t[1]
    p = 0
    if 0 <= x - 1:
        p = cum[x] - cum[x - 1]
    if x != y:
        p += cum[y] - cum[x]
    print(p)