GIven two positive integers N and K. You have to find the Kth smallest factor of N. A factor of N is a positive integer which divides N. Output the Kth smallest factor of N if it exists otherwise print -1.
 
Example 1:
Input : N = 4 , K = 2
Output: 2
Explanation:
All factors of 4 are 1,2 and 4. Out of
these 2 is the 2nd smallest.
Example 2:
Input : N = 4 , K = 3
Output: 4
Explanation:
All factors of 4 are 1,2 and 4. Out of
these 4 is the 3rd smallest.
 
Your Task:
You don't need to read input or print anything. Your task is to complete the function kThSmallestFactor() which takes 2 Integers N and K as input and returns the answer.
 
Expected Time Complexity: O(sqrt(N))
Expected Auxiliary Space: O(1)
 
Constraints:
1 <= N <= 10^{6}
1 <= K <= 10^{6}

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Mathematics

Starter code: #User function Template for python3

class Solution:
    def kThSmallestFactor(self, N , K):
        # code here 

Solutions:
class Solution:

	def kThSmallestFactor(self, N, K):
		factors = []
		for i in range(1, int(N ** 0.5) + 1):
			if N % i == 0:
				factors.append(i)
				if i != N // i:
					factors.append(N // i)
		factors.sort()
		if K > len(factors):
			return -1
		else:
			return factors[K - 1]


class Solution:

	def kThSmallestFactor(self, n, k):
		from math import ceil, sqrt
		v = []
		p = int(sqrt(n)) + 1
		for i in range(1, p, 1):
			if n % i == 0:
				v.append(i)
				if i != sqrt(n):
					v.append(n // i)
		v.sort(reverse=False)
		if k > len(v):
			return -1
		else:
			return v[k - 1]


import math

class Solution:

	def kThSmallestFactor(self, N, K):
		n = int(math.sqrt(N)) + 1
		factor = []
		for i in range(1, n):
			if N % i == 0:
				factor.append(i)
				if N // i != i:
					factor.append(N // i)
		factor.sort()
		if K > len(factor):
			return -1
		return factor[K - 1]


class Solution:

	def kThSmallestFactor(self, N, K):
		from math import sqrt, ceil
		F = []
		MX = ceil(sqrt(N))
		for i in range(1, MX):
			if N % i == 0:
				F.append(i)
		CNT = 2 * len(F)
		if MX * MX == N:
			F.append(MX)
			CNT += 1
		if CNT < K:
			return -1
		if K <= CNT // 2:
			return F[K - 1]
		else:
			return N // F[CNT - K]


class Solution:

	def kThSmallestFactor(self, N, K):
		t = 0
		for i in range(1, N // 2 + 1):
			if N % i == 0:
				t += 1
				if t == K:
					return i
		t += 1
		if t == K:
			return N
		else:
			return -1


import math

class Solution:

	def kThSmallestFactor(self, N, K):
		count = 1
		if K == 1:
			return 1
		for i in range(2, N // 2 + 1):
			if N % i == 0:
				count += 1
			if count == K:
				return i
		count += 1
		if count == K:
			return N
		elif count < K:
			return -1


class Solution:

	def kThSmallestFactor(self, N, K):
		(l, end) = ([], int(N ** 0.5) + 1)
		for i in range(1, end):
			if N % i == 0:
				l.append(i)
				l.append(N // i)
		s = list(set(l))
		s.sort()
		if K > len(s):
			return -1
		return s[K - 1]


class Solution:

	def kThSmallestFactor(self, N, K):
		s = set()
		for i in range(1, int(N ** 0.5) + 1):
			if N % i == 0:
				s.add(i)
				s.add(N // i)
		s = sorted(list(s))
		if K > len(s):
			return -1
		return s[K - 1]


import math

class Solution:

	def kThSmallestFactor(self, n, k):
		x = []
		for i in range(1, int(math.sqrt(n)) + 1):
			if n % i == 0:
				x.append(i)
		a = []
		for i in range(len(x)):
			if int(n / x[-i - 1]) == x[-i - 1]:
				continue
			a.append(int(n / x[-i - 1]))
		x.extend(a)
		if k > len(x):
			return -1
		else:
			return x[k - 1]


class Solution:

	def kThSmallestFactor(self, N, K):
		import math
		l = []
		x = int(math.sqrt(N))
		for i in range(1, x + 1):
			if N % i == 0:
				l.append(i)
		p = len(l)
		if l[-1] * l[-1] != N:
			for i in range(p - 1, -1, -1):
				l.append(N / l[i])
		else:
			for i in range(p - 2, -1, -1):
				l.append(N / l[i])
		if K > len(l):
			return -1
		else:
			return int(l[K - 1])


from math import sqrt

class Solution:

	def kThSmallestFactor(self, N, k):
		div = []
		for i in range(1, int(sqrt(N)) + 1, 1):
			if N % i == 0:
				div.append(i)
				if i != sqrt(N):
					div.append(int(N / i))
		div.sort(reverse=False)
		if k > len(div):
			return -1
		return div[k - 1]


class Solution:

	def kThSmallestFactor(self, N, K):
		from math import sqrt
		sq = int(sqrt(N))
		if K == 1:
			return 1
		K = K - 1
		for i in range(2, sq + 1):
			if N % i == 0:
				fact1 = i
				K = K - 1
				if K == 0:
					return fact1
		if sq * sq == N:
			sq -= 1
		for i in range(sq, 1, -1):
			if N % i == 0:
				fact1 = N // i
				K = K - 1
				if K == 0:
					return fact1
		K = K - 1
		if K == 0:
			return N
		return -1


from math import sqrt

class Solution:

	def kThSmallestFactor(self, N, K):
		l = []
		for i in range(1, int(sqrt(N)) + 1):
			if N % i == 0:
				l.append(i)
				if i * i != N:
					l.append(N // i)
		l.sort()
		if K <= len(l):
			return l[K - 1]
		else:
			return -1


import math

class Solution:

	def kThSmallestFactor(self, N, k):
		res = []
		for i in range(1, int(math.sqrt(N)) + 1):
			if N % i == 0:
				if N / i != i:
					res += [i, int(N / i)]
				else:
					res += [i]
		res.sort()
		try:
			return res[k - 1]
		except:
			return -1


class Solution:

	def kThSmallestFactor(self, N, K):
		l1 = []
		l2 = []
		i = 1
		while i * i <= N:
			if N % i == 0:
				l1.append(i)
				if i != N // i:
					l2.append(N // i)
			i += 1
		for x in l2[::-1]:
			l1.append(x)
		if K > len(l1):
			return -1
		return l1[K - 1]


class Solution:

	def kThSmallestFactor(self, N, K):
		l1 = []
		i = 1
		while i * i <= N:
			if N % i == 0:
				l1.append(i)
				if i != N // i:
					l1.append(N // i)
			i += 1
		l1 = sorted(l1)
		if K > len(l1):
			return -1
		return l1[K - 1]


class Solution:

	def kThSmallestFactor(self, n, p):
		res = []
		for i in range(1, n + 1):
			if n % i == 0:
				a = i
				b = n // i
				if a <= b:
					res.append(a)
					res.append(b)
				else:
					break
		res = list(set(res))
		res.sort()
		m = len(res)
		if p <= m:
			return res[p - 1]
		return -1


class Solution:

	def kThSmallestFactor(self, N, K):
		if N == 1:
			return 1
		arr = [1, N]
		for i in range(2, int(N ** (1 / 2)) + 1):
			if N % i == 0:
				a = N // i
				if a == i:
					arr = arr[:len(arr) // 2] + [i] + arr[len(arr) // 2:]
				else:
					arr = arr[:len(arr) // 2] + [i, a] + arr[len(arr) // 2:]
		if K > len(arr):
			return -1
		return arr[K - 1]


import math
import collections

class Solution:

	def kThSmallestFactor(self, N, K):
		st = collections.OrderedDict()
		n = int(math.sqrt(N)) + 1
		for i in range(1, n):
			if N % i == 0:
				st[i] = i
				st[N // i] = N // i
		ans = list(st.values())
		ans.sort()
		if K > len(ans):
			return -1
		else:
			return ans[K - 1]


class Solution:

	def kThSmallestFactor(self, N, K):
		if K == 1:
			return 1
		ctr = 1
		for i in range(2, N // 2 + 1, 1):
			if N % i == 0:
				ctr = ctr + 1
				if ctr == K:
					return i
		if ctr + 1 == K:
			return N
		return -1


class Solution:

	def kThSmallestFactor(self, N, K):
		count = 0
		for val in range(1, N // 2 + 1):
			if N % val == 0:
				count += 1
				if count == K:
					return val
		if count + 1 == K:
			return N
		else:
			return -1


class Solution:

	def kThSmallestFactor(self, N, K):
		l = []
		r = int(N ** 0.5)
		s = set()
		for i in range(1, r + 1):
			if N % i == 0:
				s.add(i)
				s.add(N // i)
		s = list(s)
		s.sort()
		try:
			return s[K - 1]
		except:
			return -1


import math

class Solution:

	def kThSmallestFactor(self, N, K):
		sq = int(math.sqrt(N))
		count = 0
		vals = []
		for i in range(1, sq + 1):
			if N % i == 0:
				count += 1
				vals.append(N // i)
			if count == K:
				return i
		if N == sq * sq:
			if count - K < 0 and K + 1 <= 2 * count:
				return vals[count - K - 1]
		elif count - K < 0 and K <= 2 * count:
			return vals[count - K]
		return -1


import math

class Solution:

	def kThSmallestFactor(self, N, K):
		c = 0
		d = []
		for i in range(1, int(math.sqrt(N)) + 1):
			if N % i == 0:
				if N / i == i:
					d.append(i)
					c += 1
				else:
					d.append(i)
					d.append(int(N / i))
					c += 2
		d.sort()
		if K > c:
			return -1
		return d[K - 1]
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		(N, K) = map(int, input().split())
		ob = Solution()
		print(ob.kThSmallestFactor(N, K))


import math

class Solution:

	def kThSmallestFactor(self, n, k):
		s = math.sqrt(n)
		for i in range(1, int(s) + 1):
			if n % i == 0:
				k -= 1
				if k == 0:
					return i
		if s == int(s):
			s = int(s) - 1
		for i in range(int(s), 0, -1):
			if n % i == 0:
				k -= 1
				if k == 0:
					return n // i
		return -1
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		(N, K) = map(int, input().split())
		ob = Solution()
		print(ob.kThSmallestFactor(N, K))


class Solution:

	def kThSmallestFactor(self, N, K):
		x = []
		c = 0
		for i in range(1, int(N ** 0.5) + 1):
			if N % i == 0:
				if N / i == i:
					x.append(i)
					c = c + 1
				else:
					x.append(i)
					x.append(int(N / i))
					c = c + 2
		x = sorted(x)
		if K > c:
			return -1
		else:
			return x[K - 1]
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		(N, K) = map(int, input().split())
		ob = Solution()
		print(ob.kThSmallestFactor(N, K))


class Solution:

	def kThSmallestFactor(self, N, K):
		ans = 0
		for i in range(1, N // 2 + 1):
			if N % i == 0:
				ans += 1
				if ans == K:
					return i
		ans += 1
		if ans == K:
			return N
		else:
			return -1
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		(N, K) = map(int, input().split())
		ob = Solution()
		print(ob.kThSmallestFactor(N, K))


import collections
import math

class Solution:

	def kThSmallestFactor(self, N, K):
		factors = collections.deque([])
		temp = int(math.sqrt(N))
		for i in range(temp, 0, -1):
			reminder = N % i
			factor1 = N // i
			factor2 = i
			if reminder == 0:
				if factor1 != factor2:
					factors.append(factor1)
					factors.appendleft(factor2)
				else:
					factors.append(factor1)
		len_factors = len(factors)
		if K - 1 < len_factors:
			return factors[K - 1]
		return -1
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		(N, K) = map(int, input().split())
		ob = Solution()
		print(ob.kThSmallestFactor(N, K))


class Solution:

	def kThSmallestFactor(self, N, k):
		l = []
		p = 0
		for i in range(1, N // 2 + 1):
			if N % i == 0:
				p = p + 1
				if p == k:
					return i
		p = p + 1
		if p == k:
			return N
		return -1
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		(N, K) = map(int, input().split())
		ob = Solution()
		print(ob.kThSmallestFactor(N, K))


class Solution:

	def kThSmallestFactor(self, N, K):
		count = 0
		if N == 1:
			if K == 1:
				return 1
			else:
				return -1
		n = int(pow(N, 0.5))
		for i in range(1, n + 1):
			if N % i == 0:
				count += 1
			if count == K:
				return i
		count = 2 * count
		if n * n == N:
			count -= 1
		count = count - K + 1
		i = 1
		while i * i <= N:
			if N % i == 0:
				count -= 1
			if count == 0:
				return N // i
			i += 1
		return -1


class Solution:

	def kThSmallestFactor(self, N, K):
		count = 0
		for i in range(1, int(N ** 0.5) + 1):
			if N % i == 0:
				count += 1
				if count == K:
					return i
		if count < K:
			for i in range(int(N ** 0.5), 0, -1):
				if N % i == 0:
					if N // i > int(N ** 0.5):
						count += 1
						if count == K:
							return N // i
			return -1


import math

class Solution:

	def kThSmallestFactor(self, n, k):
		i = 1
		l = []
		while i <= int(math.sqrt(n)):
			if n % i == 0:
				if n / i == i:
					l.append(i)
					s = True
					break
				else:
					l.append(i)
			i += 1
		l1 = len(l)
		if len(l) < k:
			for i in range(l1 - 1, -1, -1):
				if n / l[i] == l[i]:
					continue
				l.append(int(n / l[i]))
		if k > len(l):
			return -1
		else:
			return l[k - 1]


class Solution:

	def kThSmallestFactor(self, N, K):
		fact = [1, N]
		sqr = round(N ** (1 / 2)) + 2
		for k in range(2, sqr):
			if N % k == 0:
				if k not in fact:
					fact.append(k)
				if N // k not in fact:
					fact.append(N // k)
		if K - 1 < len(fact):
			fact = sorted(fact)
			return fact[K - 1]
		else:
			return -1


class Solution:

	def kThSmallestFactor(self, N, k):
		f = 0
		for i in range(1, N // 2 + 1):
			if N % i == 0:
				f += 1
				if f == k:
					return i
		f += 1
		if f == k:
			return N
		return -1


class Solution:

	def kThSmallestFactor(self, N, K):
		l = []
		c = 0
		for i in range(1, int(pow(N, 1 / 2)) + 1):
			if N % i == 0:
				if N / i == i:
					l.append(i)
					c = c + 1
				else:
					l.append(i)
					l.append(int(N / i))
					c = c + 2
		l.sort()
		if K > c:
			return -1
		else:
			return l[K - 1]


import math
import heapq

class Solution:

	def kThSmallestFactor(self, N, K):
		t = math.floor(math.sqrt(N))
		i = 1
		ans = []
		while i <= t:
			if N % i == 0:
				if N // i == i:
					ans.append(i)
				else:
					ans.append(i)
					ans.append(N // i)
			i += 1
		if K <= len(ans):
			ans.sort()
			return ans[K - 1]
		else:
			return -1


class Solution:

	def kThSmallestFactor(self, N, K):
		a = []
		b = []
		for i in range(1, int(N ** 0.5) + 1):
			if N % i == 0:
				a.append(i)
				b.append(N // i)
		b = b[::-1]
		if a[-1] == b[0]:
			a.pop()
		a = a + b
		if K - 1 >= len(a):
			return -1
		else:
			return a[K - 1]


import math

class Solution:

	def kThSmallestFactor(self, N, K):
		v = []
		p = int(math.sqrt(N)) + 1
		for i in range(1, p, 1):
			if N % i == 0:
				v.append(i)
				if i != math.sqrt(N):
					v.append(N / i)
		v.sort(reverse=False)
		if K > len(v):
			return -1
		else:
			return int(v[K - 1])


import math

class Solution:

	def kThSmallestFactor(self, n, k):
		ans = []
		i = 1
		while i <= int(math.sqrt(n)):
			if n % i == 0:
				if n / i == i:
					ans.append(i)
				else:
					ans.append(i)
					ans.append(int(n / i))
			i += 1
		ans.sort()
		if len(ans) >= k:
			return ans[k - 1]
		else:
			return -1


import math

class Solution:

	def kThSmallestFactor(self, N, K):
		i = 1
		cur = -1
		while i * i < N and K != 0:
			if N % i == 0:
				K -= 1
				cur = i
			i += 1
		i = int(math.sqrt(N))
		while i > 0 and K != 0:
			if N % i == 0:
				K -= 1
				cur = int(N / i)
			i -= 1
		if K == 0:
			return cur
		else:
			return -1


import math

class Solution:
	l = []

	def kThSmallestFactor(self, N, k):
		i = 1
		l = []
		if N == 1:
			return 1
		while i <= math.sqrt(N):
			if N % i == 0:
				if N / i != i:
					l.append(i)
					l.append(N / i)
				else:
					l.append(i)
			i += 1
		l.sort()
		if len(l) < k:
			return -1
		return int(l[k - 1])


from math import *

class Solution:

	def kThSmallestFactor(self, N, K):
		l = []
		for i in range(1, round(N ** (1 / 2)) + 1):
			if N % i == 0:
				if N // i == i:
					l.append(i)
				else:
					l.append(i)
					l.append(N // i)
		if K <= len(l):
			return sorted(l)[K - 1]
		else:
			return -1


class Solution:

	def kThSmallestFactor(self, N, K):
		res = []
		i = 1
		while i * i <= N:
			if N % i == 0:
				res.append(i)
				if N // i not in res:
					res.append(N // i)
			i += 1
		if len(res) < K:
			return -1
		else:
			res.sort()
			return res[K - 1]


class Solution:

	def kThSmallestFactor(self, N, K):
		import math
		lst = []
		i = 1
		while i <= math.sqrt(N):
			if N % i == 0:
				if N // i == i:
					lst.append(i)
				else:
					lst.append(i)
					lst.append(N // i)
			i += 1
		try:
			lst.sort()
			return lst[K - 1]
		except:
			return -1


import math

class Solution:

	def kThSmallestFactor(self, N, K):
		if K == 1:
			return 1
		c = 0
		l = []
		s = int(math.sqrt(N))
		for i in range(1, s + 1):
			if N % i == 0:
				if N // i == s:
					l.append(i)
					c = c + 1
				else:
					l.append(i)
					l.append(int(N // i))
					c = c + 2
		l.sort()
		if K > c:
			return -1
		else:
			return l[K - 1]


class Solution:

	def kThSmallestFactor(self, N, K):
		p = 2
		c = [1]
		while p * p <= N:
			if N % p == 0:
				c.append(p)
				if p * p != N:
					c.append(N // p)
			p = p + 1
		c.append(N)
		c.sort()
		if len(c) < K:
			return -1
		return c[K - 1]


class Solution:

	def kThSmallestFactor(self, N, K):
		li = []
		for i in range(1, int(pow(N, 1 / 2) + 1)):
			if N % i == 0:
				li.append(i)
				if N / i != i:
					li.append(N // i)
		if K > len(li):
			return -1
		li.sort()
		return li[K - 1]


class Solution:

	def kThSmallestFactor(self, N, K):
		l = [1]
		l1 = []
		for i in range(2, int(N ** 0.5) + 1):
			if N % i == 0:
				if N // i == i:
					l.append(i)
				else:
					l.append(i)
					l.append(N // i)
		l.append(N)
		l.sort()
		if K <= len(l):
			return l[K - 1]
		else:
			return -1


class Solution:

	def kThSmallestFactor(self, N, k):
		n = int(N ** 0.5)
		i = 1
		while i <= n:
			if N % i == 0:
				k -= 1
			if k == 0:
				return i
			i += 1
		i = n
		while i > 0:
			if N % i == 0 and i != N // i:
				k -= 1
			if k == 0:
				return N // i
			i -= 1
		return -1


import math

class Solution:

	def kThSmallestFactor(self, N, K):
		fact = []
		for i in range(1, math.ceil(math.sqrt(N + 1))):
			if N % i == 0:
				f = N // i
				if f != i:
					fact.append(f)
				fact.append(i)
		fact.sort()
		if K > len(fact):
			return -1
		else:
			return fact[K - 1]


class Solution:

	def kThSmallestFactor(self, N, K):
		if K > N:
			return -1
		if K == 1:
			return 1
		output = -1
		i = 1
		while i * i < N:
			if K == 0:
				return output
			if N % i == 0:
				K -= 1
				output = i
			i += 1
		for num in range(int(N ** 0.5), 0, -1):
			if K == 0:
				return output
			elif N % num == 0:
				K -= 1
				output = N // num
		if K >= 1:
			return -1
		return output