save-girlfriend

Kuldeep and his girlfriend Cristie are both huge math nerds, so for their first anniversary he decides to take her out on a romantic getaway to Mathland, the city of mathematics and love. 

Now Kuldeep's arch-nemesis Rishabh, jealous of the perfect relationship between Kuldeep and Cristie, kidnaps Kuldeep's girl and imprisons her at the top floor of his dungeon.

Surprisingly the dungeon is in an apartment complex of n floors, numbered 1 to n, and being short on cash Rishabh can only lease some floors (continious) for his dungeon from floor a to floor b (inclusive).

Also to make sure so that Kulddep cannot come and rescue his girlfriend, Rishabh places guards on some of the floors he has leased.

Being a bit eccentric, he only places guards on those floors from a to b (inclusive), where the floor number has highest number of divisors.

Kuldeep apart from being a math genius is extremely proficient in the art of Wu Shu, a type of Chinese martial art, so it's easy for him to defeat the guards but he still takes 1 unit of health damage per guarded floor and Kuldeep dies if his health ever reaches 0 or less.

Your task is to help Kuldeep find the minimum amount of health units he needs to reach Cristie.

Input : 

first line contain number of test cases T , next T line contains two numbers a and b.

Output :

Output minimum amount of health units he needs to reach Cristie.

Constraints:
1 ≤ T ≤ 100
1 ≤ n(number of floors) ≤ 10^8
0 ≤ b-a ≤ 10^4

SAMPLE INPUT
2
2 9
1 10SAMPLE OUTPUT
3
4Explanation

In first test case with a=2 and b=9, 6 and 8 are the floors with numbers which have highest number of divisors.So guards are placed at 2 floors only, therefore Kuldeep needs minimum 3 units of health to reach Cristie.

Similarly for second test case with a=1 and b=10, floor numbers with highest number of divisors are 6,8 and 10, so minimum health units required is 4.

Source: hackerearth | Difficulty: MEDIUM
Tags: Number theory

Mathematics


Solutions:
def primes_sieve1(limit):
	limitn = limit+1
	primes = dict()
	for i in range(2, limitn): primes[i] = True

	for i in primes:
		factors = list(range(i,limitn, i))
		for f in factors[1:]:
			primes[f] = False
	return [i for i in primes if primes[i]==True]
primes = primes_sieve1(130)
def smartDivisorGenerator(n):
	limit = 1
	for val in primes:
		counter = 1
		while True:
			if n%val == 0:
				counter+=1
				n = n/val
			else:
				break;
		limit = limit * counter
	return limit
for i in range(eval(input())):
	l=[int(x) for x in input().split()]
	a = 0
	b = 0
	for val in range(l[0], l[1]+1):
		div = smartDivisorGenerator(val)
		if div > a:
			b = 0
			a = div
			b +=1
		elif  div == a:
			b+=1
	print((str(b+1)))


primes = [2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101,103]
pre = [1, 2, 2, 3, 2, 4, 2, 4, 3, 4, 2, 6, 2, 4, 4, 5, 2, 6, 2, 6, 4, 4, 2, 8, 3, 4, 4, 6, 2, 8, 2, 6, 4, 4, 4, 9, 2, 4, 4, 8, 2, 8, 2, 6, 6, 4, 2, 10, 3, 6, 4, 6, 2, 8, 4, 8, 4, 4, 2, 12, 2, 4, 6, 7, 4, 8, 2, 6, 4, 8, 2, 12, 2, 4, 6, 6, 4, 8, 2, 10, 5, 4, 2, 12, 4, 4, 4, 8, 2, 12, 4, 6, 4, 4, 4, 12, 2, 6, 6, 9, 2, 8, 2, 8]

def smartDivisorGenerator(n):
	limit = 1
	if n < 104:
		return pre[n-1]
	for val in primes:
		counter = 1
		while True:
			if n%val == 0:
				counter+=1
				n = n/val
			else:
				break;
		limit = limit * counter
	return limit

def get_result(x,y):
	highest = 0
	value = 0
	for val in range(x, y+1):
		div = smartDivisorGenerator(val)
		if div > highest:
			value = 0
			highest = div
			value +=1
		elif  div == highest:
			value+=1
	return value+1

T = eval(input())
for res in range(T):
	a=input().split()
	print(get_result(int(a[0]),int(a[1])))




primes = [2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101,103,107,109,113,127]

def smartDivisorGenerator(n):
	limit = 1
	for val in primes:
		counter = 1
		while True:
			if n%val == 0:
				counter+=1
				n = n/val
			else:
				break;
		limit = limit * counter
	return limit

def get_result(x,y):
	highest = 0
	value = 0
	for val in range(x, y+1):
		div = smartDivisorGenerator(val)
		if div > highest:
			value = 0
			highest = div
			value +=1
		elif  div == highest:
			value+=1
	return value+1

T = eval(input())
for res in range(T):
	a=input().split()
	print(get_result(int(a[0]),int(a[1])))




primes = [2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101,103,107,109,113,127]

def smartDivisorGenerator(n):
	limit = 1
	for val in primes:
		counter = 1
		while True:
			if n%val == 0:
				counter+=1
				n = n/val
			else:
				break;
		limit = limit * counter
	return limit


def get_result(x):
	highest = 0
	value = 0
	for val in range(x[0], x[1]+1):
		div = smartDivisorGenerator(val)
		if div > highest:
			value = 0
			highest = div
			value +=1
		elif  div == highest:
			value+=1
	return str(value+1)

T = eval(input())
for res in range(T):
	print(get_result(list(map(int, input().split()))))




primes = [2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101,103,107,109,113,127]

def smartDivisorGenerator(n):
	limit = 1
	for val in primes:
		counter = 1
		while True:
			if n%val == 0:
				counter+=1
				n = n/val
			else:
				break;
		limit = limit * counter
	return limit

def get_divisor(n):
	return smartDivisorGenerator(n)

def get_result(x):
	highest = 0
	value = 0
	for val in range(x[0], x[1]+1):
		div = get_divisor(val)
		if div > highest:
			value = 0
			highest = div
			value +=1
		elif  div == highest:
			value+=1
	return str(value+1)

T = eval(input())
for res in range(T):
	print(get_result(list(map(int, input().split()))))




primes = [2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101,103]
pre = [1, 2, 2, 3, 2, 4, 2, 4, 3, 4, 2, 6, 2, 4, 4, 5, 2, 6, 2, 6, 4, 4, 2, 8, 3, 4, 4, 6, 2, 8, 2, 6, 4, 4, 4, 9, 2, 4, 4, 8, 2, 8, 2, 6, 6, 4, 2, 10, 3, 6, 4, 6, 2, 8, 4, 8, 4, 4, 2, 12, 2, 4, 6, 7, 4, 8, 2, 6, 4, 8, 2, 12, 2, 4, 6, 6, 4, 8, 2, 10, 5, 4, 2, 12, 4, 4, 4, 8, 2, 12, 4, 6, 4, 4, 4, 12, 2, 6, 6, 9, 2, 8, 2, 8]

def smartDivisorGenerator(n):
	limit = 1
	if n in primes:
		return 2
	if n < 104:
		return pre[n-1]
	for val in primes:
		counter = 1
		while True:
			if n%val == 0:
				counter+=1
				n = n/val
			else:
				break;
		limit = limit * counter
	return limit

def get_result(x,y):
	highest = 0
	value = 0
	for val in range(x, y+1):
		div = smartDivisorGenerator(val)
		if div > highest:
			value = 0
			highest = div
			value +=1
		elif  div == highest:
			value+=1
	return value+1

T = eval(input())
for res in range(T):
	a=input().split()
	print(get_result(int(a[0]),int(a[1])))




primes = [2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101,103]

def smartDivisorGenerator(n):
	limit = 1
	for val in primes:
		counter = 1
		while True:
			if n%val == 0:
				counter+=1
				n = n/val
			else:
				break;
		limit = limit * counter
	return limit

def get_result(x,y):
	highest = 0
	value = 0
	for val in range(x, y+1):
		div = smartDivisorGenerator(val)
		if div > highest:
			value = 0
			highest = div
			value +=1
		elif  div == highest:
			value+=1
	return value+1

T = eval(input())
for res in range(T):
	a=input().split()
	print(get_result(int(a[0]),int(a[1])))




primes = [2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101,103,107,109,113,127]

def smartDivisorGenerator(n):
	limit = 1
	for val in primes:
		counter = 1
		while True:
			if n%val == 0:
				counter+=1
				n = n/val
			else:
				break;
		limit = limit * counter
	return limit

def get_result(x):
	highest = 0
	value = 0
	for val in range(x[0], x[1]+1):
		div = smartDivisorGenerator(val)
		if div > highest:
			value = 0
			highest = div
			value +=1
		elif  div == highest:
			value+=1
	return value+1

T = eval(input())
for res in range(T):
	print(get_result(list(map(int, input().split()))))




primes = [2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101,103]

def smartDivisorGenerator(n):
	limit = 1
	for val in primes:
		counter = 1
		while True:
			if n%val == 0:
				counter+=1
				n = n/val
			else:
				break;
		limit = limit * counter
	return limit

def get_result(x,y):
	highest = 0
	value = 0
	for val in range(x, y+1):
		div = smartDivisorGenerator(val)
		if div > highest:
			value = 0
			highest = div
			value +=1
		elif  div == highest:
			value+=1
	return value+1

T = eval(input())
for res in range(T):
	a=input().split()
	print(get_result(int(a[0]),int(a[1])))




primes = [2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101,103,107,109,113,127]

def smartDivisorGenerator(n):
	limit = 1
	for val in primes:
		counter = 1
		while True:
			if n%val == 0:
				counter+=1
				n = n/val
			else:
				break;
		limit = limit * counter
	return limit

def get_result(x):
	highest = 0
	value = 0
	for val in range(x[0], x[1]+1):
		div = smartDivisorGenerator(val)
		if div > highest:
			value = 0
			highest = div
			value +=1
		elif  div == highest:
			value+=1
	return value+1

T = eval(input())
for res in range(T):
	print(get_result(list(map(int, input().split()))))




primes = [2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101,103]

def smartDivisorGenerator(n):
	limit = 1
	if n in primes:
		return 2
	for val in primes:
		counter = 1
		while True:
			if n%val == 0:
				counter+=1
				n = n/val
			else:
				break;
		limit = limit * counter
	return limit

def get_result(x,y):
	highest = 0
	value = 0
	for val in range(x, y+1):
		div = smartDivisorGenerator(val)
		if div > highest:
			value = 0
			highest = div
			value +=1
		elif  div == highest:
			value+=1
	return value+1

T = eval(input())
for res in range(T):
	a=input().split()
	print(get_result(int(a[0]),int(a[1])))