
"""simple docstring"""
from __future__ import annotations

import math





def    _lowerCAmelCase    (     lowerCamelCase__							:							int				)  ->    List[str]:




		if num <= 0:
				_SCREAMING_SNAKE_CASE   :				Optional[Any]							    = f'''{num}: Invalid input, please enter a positive integer.'''
				raise ValueError(lowerCamelCase__				)

		_SCREAMING_SNAKE_CASE   :				Optional[Any]							    = [True] * (num + 1)
		_SCREAMING_SNAKE_CASE   :				List[str]							    = []
		_SCREAMING_SNAKE_CASE   :				Any							    = 2
		_SCREAMING_SNAKE_CASE   :				Union[str, Any]							    = int(math.sqrt(lowerCamelCase__				)				)

		while start <= end:
				# If start is a prime
				if sieve[start] is True:
						prime.append(lowerCamelCase__				)

						# Set multiples of start be False
						for i in range(start * start,						num + 1,						lowerCamelCase__				):
								if sieve[i] is True:
										_SCREAMING_SNAKE_CASE   :				List[str]							    = False

				start += 1

		for j in range(end + 1,						num + 1				):
				if sieve[j] is True:
						prime.append(lowerCamelCase__				)

		return prime


if __name__ == "__main__":
						print(prime_sieve(int(input('''Enter a positive integer: ''').strip())))





"""simple docstring"""
from collections.abc import Iterable
from typing import Any
class 			UpperCamelCase      :
     def __init__(     self  ,     snake_case__ = None				):




       """simple docstring"""


       _SCREAMING_SNAKE_CASE   :				List[str]							    = value
       _SCREAMING_SNAKE_CASE   :				Node | None							    = None  # Added in order to delete a node easier
       _SCREAMING_SNAKE_CASE   :				Node | None							    = None
       _SCREAMING_SNAKE_CASE   :				Node | None							    = None




     def __repr__(     self				):




       """simple docstring"""


       from pprint import pformat

       if self.left is None and self.right is None:
         return str(self.value				)
       return pformat({F'''{self.value}''': (self.left, self.right)}  ,     indent=1				)
class 			UpperCamelCase      :
     def __init__(     self  ,     snake_case__ = None				):




       """simple docstring"""


       _SCREAMING_SNAKE_CASE   :				List[str]							    = root
     def __str__(     self				):




       """simple docstring"""


       return str(self.root				)
     def 				__SCREAMING_SNAKE_CASE							(     self  ,     snake_case__  ,     snake_case__				):




       """simple docstring"""


       if new_children is not None:  # reset its kids
         _SCREAMING_SNAKE_CASE   :				Dict							    = node.parent
       if node.parent is not None:  # reset its parent
         if self.is_right(snake_case__				):  # If it is the right children
           _SCREAMING_SNAKE_CASE   :				Any							    = new_children
         else:
           _SCREAMING_SNAKE_CASE   :				Union[str, Any]							    = new_children
       else:
         _SCREAMING_SNAKE_CASE   :				Any							    = new_children
     def 				__SCREAMING_SNAKE_CASE							(     self  ,     snake_case__				):




       """simple docstring"""


       if node.parent and node.parent.right:
         return node == node.parent.right
       return False
     def 				__SCREAMING_SNAKE_CASE							(     self				):




       """simple docstring"""


       return self.root is None
     def 				__SCREAMING_SNAKE_CASE							(     self  ,     snake_case__				):




       """simple docstring"""


       _SCREAMING_SNAKE_CASE   :				Optional[int]							    = Node(snake_case__				)  # create a new Node
       if self.empty():  # if Tree is empty
         _SCREAMING_SNAKE_CASE   :				str							    = new_node  # set its root
       else:  # Tree is not empty
         _SCREAMING_SNAKE_CASE   :				Dict							    = self.root  # from root
         if parent_node is None:
           return
         while True:  # While we don't get to a leaf
           if value < parent_node.value:  # We go left
             if parent_node.left is None:
               _SCREAMING_SNAKE_CASE   :				Union[str, Any]							    = new_node  # We insert the new node in a leaf
               break
             else:
               _SCREAMING_SNAKE_CASE   :				int							    = parent_node.left
           else:
             if parent_node.right is None:
               _SCREAMING_SNAKE_CASE   :				str							    = new_node
               break
             else:
               _SCREAMING_SNAKE_CASE   :				Optional[int]							    = parent_node.right
         _SCREAMING_SNAKE_CASE   :				Any							    = parent_node
     def 				__SCREAMING_SNAKE_CASE							(     self  ,     *snake_case__				):




       """simple docstring"""


       for value in values:
         self.__insert(snake_case__				)
     def 				__SCREAMING_SNAKE_CASE							(     self  ,     snake_case__				):




       """simple docstring"""


       if self.empty():
         raise IndexError("Warning: Tree is empty! please use another."				)
       else:
         _SCREAMING_SNAKE_CASE   :				Optional[int]							    = self.root
         # use lazy evaluation here to avoid NoneType Attribute error
         while node is not None and node.value is not value:
           _SCREAMING_SNAKE_CASE   :				List[Any]							    = node.left if value < node.value else node.right
         return node
     def 				__SCREAMING_SNAKE_CASE							(     self  ,     snake_case__ = None				):




       """simple docstring"""


       if node is None:
         if self.root is None:
           return None
         _SCREAMING_SNAKE_CASE   :				Optional[Any]							    = self.root

       if not self.empty():
         while node.right is not None:
           _SCREAMING_SNAKE_CASE   :				Dict							    = node.right
       return node
     def 				__SCREAMING_SNAKE_CASE							(     self  ,     snake_case__ = None				):




       """simple docstring"""


       if node is None:
         _SCREAMING_SNAKE_CASE   :				List[Any]							    = self.root
       if self.root is None:
         return None
       if not self.empty():
         _SCREAMING_SNAKE_CASE   :				Any							    = self.root
         while node.left is not None:
           _SCREAMING_SNAKE_CASE   :				Optional[int]							    = node.left
       return node
     def 				__SCREAMING_SNAKE_CASE							(     self  ,     snake_case__				):




       """simple docstring"""


       _SCREAMING_SNAKE_CASE   :				Dict							    = self.search(snake_case__				)  # Look for the node with that label
       if node is not None:
         if node.left is None and node.right is None:  # If it has no children
           self.__reassign_nodes(snake_case__  ,     snake_case__				)
         elif node.left is None:  # Has only right children
           self.__reassign_nodes(snake_case__  ,     node.right				)
         elif node.right is None:  # Has only left children
           self.__reassign_nodes(snake_case__  ,     node.left				)
         else:
           _SCREAMING_SNAKE_CASE   :				Dict							    = self.get_max(
               node.left				)  # Gets the max value of the left branch
           self.remove(tmp_node.value				)  # type: ignore
           _SCREAMING_SNAKE_CASE   :				List[Any]							    = (
               tmp_node.value  # type: ignore
           )  # Assigns the value to the node to delete and keep tree structure
     def 				__SCREAMING_SNAKE_CASE							(     self  ,     snake_case__				):




       """simple docstring"""


       if node is not None:
         yield node  # Preorder Traversal
         yield from self.preorder_traverse(node.left				)
         yield from self.preorder_traverse(node.right				)
     def 				__SCREAMING_SNAKE_CASE							(     self  ,     snake_case__=None				):




       """simple docstring"""


       if traversal_function is None:
         return self.preorder_traverse(self.root				)
       else:
         return traversal_function(self.root				)
     def 				__SCREAMING_SNAKE_CASE							(     self  ,     snake_case__  ,     snake_case__				):




       """simple docstring"""


       if node:
         self.inorder(snake_case__  ,     node.left				)
         arr.append(node.value				)
         self.inorder(snake_case__  ,     node.right				)




     def 				__SCREAMING_SNAKE_CASE							(     self  ,     snake_case__  ,     snake_case__				):




       """simple docstring"""


       _SCREAMING_SNAKE_CASE   :				list[int]							    = []
       self.inorder(snake_case__  ,     snake_case__				)  # append all values to list using inorder traversal
       return arr[k - 1]





def    _lowerCAmelCase    (     lowerCamelCase__							:							Node | None				)  ->    list[Node]:
  _SCREAMING_SNAKE_CASE   :				Optional[int]							    = []
  if curr_node is not None:
    _SCREAMING_SNAKE_CASE   :				int							    = postorder(curr_node.left				) + postorder(curr_node.right				) + [curr_node]
  return node_list





def    _lowerCAmelCase    (     )  ->    None:
  _SCREAMING_SNAKE_CASE   :				Any							    = (8, 3, 6, 1, 1_0, 1_4, 1_3, 4, 7)
  _SCREAMING_SNAKE_CASE   :				List[Any]							    = BinarySearchTree()
  for i in testlist:
    t.insert(lowerCamelCase__				)

  # Prints all the elements of the list in order traversal
  print(lowerCamelCase__				)

  if t.search(6				) is not None:
    print("The value 6 exists"				)
  else:
    print("The value 6 doesn't exist"				)

  if t.search(-1				) is not None:
    print("The value -1 exists"				)
  else:
    print("The value -1 doesn't exist"				)

  if not t.empty():
    print("Max Value: ",						t.get_max().value				)  # type: ignore
    print("Min Value: ",						t.get_min().value				)  # type: ignore

  for i in testlist:
    t.remove(lowerCamelCase__				)
    print(lowerCamelCase__				)


if __name__ == "__main__":
      import doctest

      doctest.testmod(verbose=True)



