fork download
copy 
  1. import math
  2.  
  3. spf = list()
  4. sieve_list = list()
  5.  
  6. def sieve(MAXN):
  7. 	# print(MAXN)
  8. 	primes = list()
  9. 	global sieve_list, spf
  10. 	sieve_list = [True for i in range(MAXN)]
  11. 	spf = [-1 for i in range(MAXN)]
  12. 	spf[0] = 0
  13. 	spf[1] = 1
  14.  
  15. 	i = 2
  16. 	while i*i <= MAXN:
  17. 		print(i)
  18. 		if sieve_list[i] == True:
  19. 			if spf[i] == -1:
  20. 				spf[i] = i
  21.  
  22. 			for x in range(i*i, MAXN, i):
  23. 				if spf[x] == -1:
  24. 					spf[x] = i
  25. 				sieve_list[x] = False
  26. 		i += 1
  27. 	# print(sieve_list)
  28. 	for i in range(2, MAXN):
  29. 		if sieve_list[i] == True:
  30. 			primes.append(i)
  31. 	print(spf)		
  32. 	return sieve_list
  33.  
  34. def get_prime_factors(x):
  35.  
  36. 	res = list()
  37. 	while x != 1:
  38. 		# print(x)
  39. 		res.append(spf[x])
  40. 		x = x//spf[x]
  41. 	return res 
  42.  
  43. if __name__ == '__main__':
  44. 	t = int(input())
  45. 	while t:
  46. 		x, k = map(int, input().split())
  47. 		# print(x, k)
  48. 		if x<k:
  49. 			print('0')
  50. 		elif x<=2 and (k==1):
  51. 			print('1')
  52. 		elif x == 3 and k == 1:
  53. 			print('1')
  54. 		elif x == 3 and k !=1:
  55. 			print('0')
  56. 		elif x == 2 and k == 2:
  57. 			print('0')
  58. 		else:
  59. 			sieve_list = sieve(x+1)
  60. 			actual_k = get_prime_factors(x)
  61. 			# print(actual_k)
  62. 			set_k = set(actual_k)
  63. 			if k == len(actual_k) or k == len(set_k):
  64. 				print('1')
  65. 			else:
  66. 				print('0')
  67. 		t -= 1
Success #stdin #stdout 0.02s 9408KB
comments (?)
stdin
copy 
5
3 1
3 2
2 1
2 2
3 1
stdout
copy 
1
0
1
0
1
https://ideone.com/LttuVC
language:
Python 3 (python  3.9.5)
created:
4 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!