micro-and-prime-prime-1

Micro just learned about prime numbers. But he quickly got bored of them, so he defined a new kind of numbers and called them Prime Prime Numbers. A number X is Prime Prime if number of prime numbers from 1 to X (inclusive) are prime. Now he wants to find out the number of Prime Prime numbers from L to R (inclusive). Help Micro with it. 

Input:
First line consists of a single integer T denoting number of test cases
Following T lines consists of two space separated integers denoting L and R

Output:
Print the number of Prime Prime Numbers for each between L and R for each test case in a new line. 

Constraints:
 1 ≤ T ≤ 10^5
 1 ≤ L, R ≤ 10^6 

SAMPLE INPUT
2
3 10
4 12

SAMPLE OUTPUT
4
5

Source: hackerearth | Difficulty: EASY
Tags: Number theory

Data structures


Solutions:
'''
# Read input from stdin and provide input before running code

name = raw_input('What is your name?\n')
print 'Hi, %s.' % name
'''

li=[]
N=1000000
def sieve():
	dic={}
	dic[2]='1'
	nop=1
	global li
	li=[0 for i in range(N+1)]
	vis=[0 for i in range(N)]
	for i in range(3,N,2):
		if vis[i]==0:
			dic[i]='1'
			# print dic
			nop=nop+1
			for j in range(i*i,N,2*i):
				vis[j]=1;
		
		li[i]=li[i-1]+1 if nop in dic else li[i-1]
		j=i+1
		li[j]=li[j-1]+1 if nop in dic else li[j-1]
	# print li
	

def calculate():
	t=int(input())
	sieve()
	for q in range(t):
		s,e=[int(x) for x in input().split()]
		# print s,e
		print(li[e]-li[s-1])
		
calculate()
			


def seive(N):
	junk = set()
	for i in range(2, N+1):
		if i in junk:
			continue	
		primes[i-1] = True
		junk.update( list(range(2*i, N+1, i)) )

n = 10**6

primes = [False] * n
seive(n)
current = 0
cur = 0
k = []
for i in range(1, n+1):
	if primes[i-1]:
		current += 1
	if primes[current-1]:
		cur += 1
	k.append(cur)

T = eval(input())
for i in range(T):
	a, b = list(map( int, input().strip().split() ))
	a -= 1
	b -= 1
	if a == 0:
		print(k[b])
	else:
		print(k[b] - k[a-1])



def seive(N):
	junk = set([1])	
	current = 0
	cur = 0
	primes = [False] * N

	for i in range(1, N+1):
		flag = True
		if i in junk:
			flag = False
		    
		if flag:
			junk.update( list(range(2*i, N+1, i)) )
			primes[i-1] = True
			current += 1
	
		if primes[current-1]:
			cur += 1
		k.append(cur)

n = 10**6
k = []
	
seive(n)

T = eval(input())
for i in range(T):
	a, b = list(map( int, input().strip().split() ))
	a -= 1
	b -= 1
	if a == 0:
		print(k[b])
	else:
		print(k[b] - k[a-1])