chef-and-prime-tree

Darshak (Dark)  likes to get fruits from trees a lot,he always like to eat those natural fruits directly from the tree.
Today he has an infinite full binary tree (each node has exactly two child's) with special properties.
Dark's tree has the following special properties :
Each node of the tree has a value of goodness.
The root of the tree is labelled as 1(value of goodness). For a node labelled v, it's left child is labelled as 2v(value of goodness)  and it's right child is labelled as 2v+1(value of goodness).
Dark wants to fulfill Q queries on this tree. 

Each query has two numbers 'x' and 'y'.He travels on the path from node 'x' to node 'y', on traversing each node has value of goodness if the value found to be a prime number  it would get subtracted while if it is composite number then it gets added.

Help Dark accomplishing this task.

Input:

First line of the input contains an integer Q denoting the number of queries. Next Q lines of the input contain Q queries (one per line) having 2 numbers 'x' and 'y'.

Output:

For each query print the value of goodness on entire traversal from node 'x' to node 'y'.

Constraints:

1 ≤ Q ≤ 5*10^3

1 ≤ x,y ≤ 5 * 10^6

Scoring :

subtask1 :

 1 ≤ x,y ≤ 10000        30 points

subtask2  :

1 ≤ x,y ≤ 5 * 10^6       70 points

Author : Darshak Mehta

SAMPLE INPUT
2
1 5
4 4

SAMPLE OUTPUT
-6
4

Source: hackerearth | Difficulty: UNKNOWN_DIFFICULTY
Tags: Tree algorithms


Solutions:
def is_prime(n):
	if n == 2 or n == 3:
		return True
	elif n < 2:
		return False
	elif n%2 == 0:
		return False

	limit = int(n**0.5) + 1 
	for i in range(3, limit, 2):
		if n%i == 0:
			return False
			
	return True

def main():
	for _ in range(eval(input())):
		x, y = list(map(int, input().split()))
		if x == y:
			if is_prime(x):
				print(-x)
			else:
				print(x)
			continue
		# For common ancestor
		root_x = []
		root_y = []
		i = x
		j = y
		
		while i:
			root_x.append(i)
			i /= 2
		while j:
			root_y.append(j)
			j /= 2	 	
		
		ca = max(set(root_x) & set(root_y))
		path = root_x[:root_x.index(ca)] + [ca] + root_y[:root_y.index(ca)]
		answer = 0	
			
		for node in path:
			if is_prime(node):
				answer -= node
			else:
				answer += node
		print(answer)
		
	return 0	

if __name__ == "__main__":
	main()	


# your code goes here

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, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509, 521, 523, 541,
547, 557, 563, 569, 571, 577, 587, 593, 599, 601, 607, 613, 617, 619, 631, 641, 643, 647, 653, 659, 661, 673, 677, 683, 691, 701, 709, 719, 727, 733, 739, 743, 751, 757, 761, 769, 773, 787, 797, 809, 811, 821, 823, 827, 829, 839, 853, 857, 859, 863, 877, 881, 883, 887, 907, 911, 919, 929, 937, 941, 947, 953, 967, 971, 977, 983, 991, 997, 1009, 1013, 1019, 1021, 1031, 1033, 1039, 1049, 1051, 1061, 1063, 1069, 1087, 1091, 1093, 1097, 1103, 1109, 1117, 1123, 1129, 1151, 1153, 1163, 1171, 1181, 1187, 1193, 1201, 1213, 1217, 1223,
1229, 1231, 1237, 1249, 1259, 1277, 1279, 1283, 1289, 1291, 1297, 1301, 1303, 1307, 1319, 1321, 1327, 1361, 1367, 1373, 1381, 1399, 1409, 1423, 1427, 1429, 1433, 1439, 1447, 1451, 1453, 1459, 1471, 1481, 1483, 1487, 1489, 1493, 1499, 1511, 1523, 1531, 1543, 1549, 1553, 1559, 1567, 1571, 1579, 1583, 1597, 1601, 1607, 1609, 1613, 1619, 1621, 1627, 1637, 1657, 1663, 1667, 1669, 1693, 1697, 1699, 1709, 1721, 1723, 1733, 1741, 1747, 1753, 1759, 1777, 1783, 1787, 1789, 1801, 1811, 1823, 1831, 1847, 1861, 1867, 1871, 1873, 1877, 1879, 1889, 1901, 1907, 1913, 1931, 1933, 1949, 1951, 1973, 1979, 1987,
1993, 1997, 1999, 2003, 2011, 2017, 2027, 2029, 2039, 2053, 2063, 2069, 2081, 2083, 2087, 2089, 2099, 2111, 2113, 2129, 2131, 2137, 2141, 2143, 2153, 2161, 2179, 2203, 2207, 2213, 2221, 2237]

def isprime(x):
	l = len(primes)
	i=0
	if x==1:
		return False
	while i<l:
		if x%primes[i]==0 and x!=primes[i]:
			return False
		i+=1
	return True

t=int(input())
while t>0:
	z = input()
	d = z.split(" ")
	x = int(d[0])
	y = int(d[1])
	total = 0
	if x==y:
		if isprime(x)==False:
			total = total + x
		else:
			total = total - x
		print(total)
		t = t-1
		continue
	
	while x!=y:
		if x>y:
			if isprime(x)==False:
				total+=x
			else:
				total-=x
			x=x/2
		else:
			if isprime(y)==False:
				total+=y
			else:
				total-=y
			y=y/2
	
	if isprime(y)==False:
		total+=y
	else:
		total-=y
	print(total)
	t-=1