
from __future__ import annotations

import unittest
from collections.abc import Iterator


class 							lowercase   :



		def __init__(					self							, A_							, A_			)    ->   Tuple:
				"""simple docstring"""
				UpperCamelCase            =	label
				UpperCamelCase            =	parent
				UpperCamelCase            =	None
				UpperCamelCase            =	None






class 							lowercase   :



		def __init__(					self			)    ->   Dict:
				"""simple docstring"""
				UpperCamelCase            =	None



		def __UpperCamelCase					(					self			)    ->   Dict:
				"""simple docstring"""
				UpperCamelCase            =	None



		def __UpperCamelCase					(					self			)    ->   List[Any]:
				"""simple docstring"""
				return self.root is None



		def __UpperCamelCase					(					self							, A_			)    ->   Any:
				"""simple docstring"""
				UpperCamelCase            =	self._put(self.root							, __snake_case			)



		def __UpperCamelCase					(					self							, A_							, A_							, A_ = None			)    ->   Any:
				"""simple docstring"""





				if node is None:
						UpperCamelCase            =	Node(__snake_case							, __snake_case			)
				else:
						if label < node.label:
								UpperCamelCase            =	self._put(node.left							, __snake_case							, __snake_case			)
						elif label > node.label:
								UpperCamelCase            =	self._put(node.right							, __snake_case							, __snake_case			)
						else:
								UpperCamelCase            =	F'''Node with label {label} already exists'''
								raise Exception(__snake_case			)

				return node



		def __UpperCamelCase					(					self							, A_			)    ->   int:
				"""simple docstring"""
				return self._search(self.root							, __snake_case			)



		def __UpperCamelCase					(					self							, A_							, A_			)    ->   List[str]:
				"""simple docstring"""





				if node is None:
						UpperCamelCase            =	F'''Node with label {label} does not exist'''
						raise Exception(__snake_case			)
				else:
						if label < node.label:
								UpperCamelCase            =	self._search(node.left							, __snake_case			)
						elif label > node.label:
								UpperCamelCase            =	self._search(node.right							, __snake_case			)

				return node



		def __UpperCamelCase					(					self							, A_			)    ->   Tuple:
				"""simple docstring"""
				UpperCamelCase            =	self.search(__snake_case			)
				if node.right and node.left:
						UpperCamelCase            =	self._get_lowest_node(node.right			)
						UpperCamelCase            =	node.left
						UpperCamelCase            =	node.right
						UpperCamelCase            =	lowest_node
						if node.right:
								UpperCamelCase            =	lowest_node
						self._reassign_nodes(__snake_case							, __snake_case			)
				elif not node.right and node.left:
						self._reassign_nodes(__snake_case							, node.left			)
				elif node.right and not node.left:
						self._reassign_nodes(__snake_case							, node.right			)
				else:
						self._reassign_nodes(__snake_case							, __snake_case			)



		def __UpperCamelCase					(					self							, A_							, A_			)    ->   List[Any]:
				"""simple docstring"""





				if new_children:
						UpperCamelCase            =	node.parent

				if node.parent:
						if node.parent.right == node:
								UpperCamelCase            =	new_children
						else:
								UpperCamelCase            =	new_children
				else:
						UpperCamelCase            =	new_children



		def __UpperCamelCase					(					self							, A_			)    ->   int:
				"""simple docstring"""





				if node.left:
						UpperCamelCase            =	self._get_lowest_node(node.left			)
				else:
						UpperCamelCase            =	node
						self._reassign_nodes(__snake_case							, node.right			)

				return lowest_node



		def __UpperCamelCase					(					self							, A_			)    ->   Tuple:
				"""simple docstring"""





				try:
						self.search(__snake_case			)
						return True
				except Exception:
						return False



		def __UpperCamelCase					(					self			)    ->   str:
				"""simple docstring"""





				if self.root is None:
						raise Exception('Binary search tree is empty'			)

				UpperCamelCase            =	self.root
				while node.right is not None:
						UpperCamelCase            =	node.right

				return node.label



		def __UpperCamelCase					(					self			)    ->   str:
				"""simple docstring"""





				if self.root is None:
						raise Exception('Binary search tree is empty'			)

				UpperCamelCase            =	self.root
				while node.left is not None:
						UpperCamelCase            =	node.left

				return node.label



		def __UpperCamelCase					(					self			)    ->   List[Any]:
				"""simple docstring"""
				return self._inorder_traversal(self.root			)



		def __UpperCamelCase					(					self							, A_			)    ->   Tuple:
				"""simple docstring"""





				if node is not None:
						yield from self._inorder_traversal(node.left			)
						yield node
						yield from self._inorder_traversal(node.right			)



		def __UpperCamelCase					(					self			)    ->   List[Any]:
				"""simple docstring"""
				return self._preorder_traversal(self.root			)



		def __UpperCamelCase					(					self							, A_			)    ->   Dict:
				"""simple docstring"""





				if node is not None:
						yield node
						yield from self._preorder_traversal(node.left			)
						yield from self._preorder_traversal(node.right			)






class 							lowercase   (						unittest.TestCase  ):



		@staticmethod
		def __UpperCamelCase					(					)    ->   Optional[Any]:
				"""simple docstring"""
				UpperCamelCase            =	BinarySearchTree()
				t.put(8			)
				t.put(3			)
				t.put(6			)
				t.put(1			)
				t.put(10			)
				t.put(14			)
				t.put(13			)
				t.put(4			)
				t.put(7			)
				t.put(5			)

				return t



		def __UpperCamelCase					(					self			)    ->   Tuple:
				"""simple docstring"""
				UpperCamelCase            =	BinarySearchTree()
				assert t.is_empty()

				t.put(8			)
				assert t.root is not None
				assert t.root.parent is None
				assert t.root.label == 8

				t.put(10			)
				assert t.root.right is not None
				assert t.root.right.parent == t.root
				assert t.root.right.label == 10

				t.put(3			)
				assert t.root.left is not None
				assert t.root.left.parent == t.root
				assert t.root.left.label == 3

				t.put(6			)
				assert t.root.left.right is not None
				assert t.root.left.right.parent == t.root.left
				assert t.root.left.right.label == 6

				t.put(1			)
				assert t.root.left.left is not None
				assert t.root.left.left.parent == t.root.left
				assert t.root.left.left.label == 1

				with self.assertRaises(__snake_case			):  # noqa: B017
						t.put(1			)



		def __UpperCamelCase					(					self			)    ->   int:
				"""simple docstring"""
				UpperCamelCase            =	self._get_binary_search_tree()

				UpperCamelCase            =	t.search(6			)
				assert node.label == 6

				UpperCamelCase            =	t.search(13			)
				assert node.label == 13

				with self.assertRaises(__snake_case			):  # noqa: B017
						t.search(2			)



		def __UpperCamelCase					(					self			)    ->   Optional[int]:
				"""simple docstring"""
				UpperCamelCase            =	self._get_binary_search_tree()

				t.remove(13			)
				assert t.root is not None
				assert t.root.right is not None
				assert t.root.right.right is not None
				assert t.root.right.right.right is None
				assert t.root.right.right.left is None

				t.remove(7			)
				assert t.root.left is not None
				assert t.root.left.right is not None
				assert t.root.left.right.left is not None
				assert t.root.left.right.right is None
				assert t.root.left.right.left.label == 4

				t.remove(6			)
				assert t.root.left.left is not None
				assert t.root.left.right.right is not None
				assert t.root.left.left.label == 1
				assert t.root.left.right.label == 4
				assert t.root.left.right.right.label == 5
				assert t.root.left.right.left is None
				assert t.root.left.left.parent == t.root.left
				assert t.root.left.right.parent == t.root.left

				t.remove(3			)
				assert t.root is not None
				assert t.root.left.label == 4
				assert t.root.left.right.label == 5
				assert t.root.left.left.label == 1
				assert t.root.left.parent == t.root
				assert t.root.left.left.parent == t.root.left
				assert t.root.left.right.parent == t.root.left

				t.remove(4			)
				assert t.root.left is not None
				assert t.root.left.left is not None
				assert t.root.left.label == 5
				assert t.root.left.right is None
				assert t.root.left.left.label == 1
				assert t.root.left.parent == t.root
				assert t.root.left.left.parent == t.root.left



		def __UpperCamelCase					(					self			)    ->   Optional[Any]:
				"""simple docstring"""
				UpperCamelCase            =	self._get_binary_search_tree()

				t.remove(3			)
				assert t.root is not None
				assert t.root.left is not None
				assert t.root.left.left is not None
				assert t.root.left.right is not None
				assert t.root.left.right.left is not None
				assert t.root.left.right.right is not None
				assert t.root.left.label == 4
				assert t.root.left.right.label == 6
				assert t.root.left.left.label == 1
				assert t.root.left.right.right.label == 7
				assert t.root.left.right.left.label == 5
				assert t.root.left.parent == t.root
				assert t.root.left.right.parent == t.root.left
				assert t.root.left.left.parent == t.root.left
				assert t.root.left.right.left.parent == t.root.left.right



		def __UpperCamelCase					(					self			)    ->   Any:
				"""simple docstring"""
				UpperCamelCase            =	self._get_binary_search_tree()
				t.empty()
				assert t.root is None



		def __UpperCamelCase					(					self			)    ->   Optional[Any]:
				"""simple docstring"""
				UpperCamelCase            =	self._get_binary_search_tree()
				assert not t.is_empty()

				t.empty()
				assert t.is_empty()



		def __UpperCamelCase					(					self			)    ->   Any:
				"""simple docstring"""
				UpperCamelCase            =	self._get_binary_search_tree()

				assert t.exists(6			)
				assert not t.exists(-1			)



		def __UpperCamelCase					(					self			)    ->   Optional[int]:
				"""simple docstring"""
				UpperCamelCase            =	self._get_binary_search_tree()

				assert t.get_max_label() == 14

				t.empty()
				with self.assertRaises(__snake_case			):  # noqa: B017
						t.get_max_label()



		def __UpperCamelCase					(					self			)    ->   str:
				"""simple docstring"""
				UpperCamelCase            =	self._get_binary_search_tree()

				assert t.get_min_label() == 1

				t.empty()
				with self.assertRaises(__snake_case			):  # noqa: B017
						t.get_min_label()



		def __UpperCamelCase					(					self			)    ->   Any:
				"""simple docstring"""
				UpperCamelCase            =	self._get_binary_search_tree()

				UpperCamelCase            =	[i.label for i in t.inorder_traversal()]
				assert inorder_traversal_nodes == [1, 3, 4, 5, 6, 7, 8, 10, 13, 14]



		def __UpperCamelCase					(					self			)    ->   Any:
				"""simple docstring"""
				UpperCamelCase            =	self._get_binary_search_tree()

				UpperCamelCase            =	[i.label for i in t.preorder_traversal()]
				assert preorder_traversal_nodes == [8, 3, 1, 6, 4, 5, 7, 10, 14, 13]






def  A			(   )  ->    None:
		'''simple docstring'''

		UpperCamelCase            =	BinarySearchTree()
		t.put(8					)
		t.put(3					)
		t.put(6					)
		t.put(1					)
		t.put(10					)
		t.put(14					)
		t.put(13					)
		t.put(4					)
		t.put(7					)
		t.put(5					)

		print(
		    '\n            8\n           / \\\n          3   10\n         / \\    \\\n        1   6    14\n           / \\   /\n          4   7 13\n           \\\n            5\n        '					)

		print('Label 6 exists:'       ,			t.exists(6					)					)
		print('Label 13 exists:'       ,			t.exists(13					)					)
		print('Label -1 exists:'       ,			t.exists(-1					)					)
		print('Label 12 exists:'       ,			t.exists(12					)					)

		# Prints all the elements of the list in inorder traversal
		UpperCamelCase            =	[i.label for i in t.inorder_traversal()]
		print('Inorder traversal:'       ,			lowercase__					)

		# Prints all the elements of the list in preorder traversal
		UpperCamelCase            =	[i.label for i in t.preorder_traversal()]
		print('Preorder traversal:'       ,			lowercase__					)

		print('Max. label:'       ,			t.get_max_label()					)
		print('Min. label:'       ,			t.get_min_label()					)

		# Delete elements
		print('\nDeleting elements 13, 10, 8, 3, 6, 14'					)
		print(
		    '\n          4\n         / \\\n        1   7\n             \\\n              5\n        '					)
		t.remove(13					)
		t.remove(10					)
		t.remove(8					)
		t.remove(3					)
		t.remove(6					)
		t.remove(14					)

		# Prints all the elements of the list in inorder traversal after delete
		UpperCamelCase            =	[i.label for i in t.inorder_traversal()]
		print('Inorder traversal after delete:'       ,			lowercase__					)

		# Prints all the elements of the list in preorder traversal after delete
		UpperCamelCase            =	[i.label for i in t.preorder_traversal()]
		print('Preorder traversal after delete:'       ,			lowercase__					)

		print('Max. label:'       ,			t.get_max_label()					)
		print('Min. label:'       ,			t.get_min_label()					)


if __name__ == "__main__":
					binary_search_tree_example()







'''simple docstring'''






import math
from collections.abc import Generator





def    lowercase_   (		lowercase__    ) ->Generator[int, None, None]:
						_snake_case: Generator	       =		(i for i in range(1					,	(max_n + 1)    ))
						for i in (n for n in numbers if n > 1):
												for j in range(2					,	lowercase__    ):
																		if (i % j) == 0:
																								break
												else:
																		yield i





def    lowercase_   (		lowercase__    ) ->Generator[int, None, None]:
						_snake_case: Generator	       =		(i for i in range(1					,	(max_n + 1)    ))
						for i in (n for n in numbers if n > 1):
												# only need to check for factors up to sqrt(i)
												_snake_case: int	       =		int(math.sqrt(lowercase__    )    ) + 1
												for j in range(2					,	lowercase__    ):
																		if (i % j) == 0:
																								break
												else:
																		yield i





def    lowercase_   (		lowercase__    ) ->Generator[int, None, None]:
						_snake_case: Generator	       =		(i for i in range(1					,	(max_n + 1)					,	2    ))
						# It's useless to test even numbers as they will not be prime
						if max_n > 2:
												yield 2  # Because 2 will not be tested, it's necessary to yield it now
						for i in (n for n in numbers if n > 1):
												_snake_case: List[str]	       =		int(math.sqrt(lowercase__    )    ) + 1
												for j in range(3					,	lowercase__					,	2    ):
																		# As we removed the even numbers, we don't need them now
																		if (i % j) == 0:
																								break
												else:
																		yield i





def    lowercase_   (		) ->Optional[int]:
						from timeit import timeit

						_snake_case: Dict	       =		'from __main__ import slow_primes, primes, fast_primes'
						print(timeit('slow_primes(1_000_000_000_000)'					,	setup=lowercase__					,	number=100_0000    )    )
						print(timeit('primes(1_000_000_000_000)'					,	setup=lowercase__					,	number=100_0000    )    )
						print(timeit('fast_primes(1_000_000_000_000)'					,	setup=lowercase__					,	number=100_0000    )    )


if __name__ == "__main__":
		A :			List[str]							   =      int(input('Calculate primes up to:\n>> ').strip())
		for ret in primes(number):
				print(ret)
		benchmark()





