ma5terminds-birthday-party

Ma5termind is having his birthday this weekend. Yeah !! You all are invited . Ma5termind wants to send an invitation to those groups of people which he finds interesting. A group of N people is said to be interesting only if the number of their possible circular permutations is divisible by N. Now, Ma5termind got confused as he is having all the groups having number of people belongs to [L,R] (both inclusive). Help him in find the minimum number of invitation cards required and win yourself a chance to attend Ma5termind's birthday party .

[INPUT:]

First line of the input contains a single integer T denoting the number of test cases. First and the only line of each test case consists of two space separated integers L and R denoting the range such that N belongs to [L,R] (both inclusive).

[OUTPUT:]

Output consists of T lines each containing the answer to the corresponding test case denoting the minimum number of invitation cards required by the Ma5termind.

[CONSTRAINTS:]

T ≤ 10^6

1 ≤ L ≤ R ≤ 10^6

SAMPLE INPUT
1
10 15SAMPLE OUTPUT
4

Explanation

For all 'n' belongs to the set {10,12,14,15} people . Group is interesting so, ma5termind will require 4 invitation cards in all.

Source: hackerearth | Difficulty: EASY
Tags: Number theory

Fundamentals


Solutions:
max= 10**6+1
p= [0]*max
def rev_seive():

	for i in range(2,max):
		if not p[i]:
			for j in range(2*i,max,i):
				p[j]=1

	p[4]=0
	p[1]=1
	for k in range(1,max):
			p[k]+=p[k-1]

rev_seive()


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


__author__ = 'Admin'
import math
limit = 1000001
list_of_primes = [0 , 1]
for i in range(2 , limit):
	list_of_primes.append(0)
i = 2

while(i*i <= limit-1):
	if list_of_primes[i] == 0:
		k = 2
		j = i * k
		while(j <= limit-1):
			list_of_primes[j] = 1
			k = k + 1
			j = i*k
	i = i + 1

# print list_of_primes
list_of_primes[4] = 0
total = 0
for i in range(1 , limit):
	if(list_of_primes[i] == 0):
		total = total + 1
		list_of_primes[i] = total
	else:
		list_of_primes[i] = list_of_primes[i-1]

# print list_of_primes

nq = int(input())
for t in range(0 , nq):
	inp = list(map(int  , input().split()))
	l = inp[0]
	r = inp[1]
	print((r - (l-1)) - (list_of_primes[r] - list_of_primes[l-1]))