from __future__ import annotations

from sys import maxsize
from typing import Generic, TypeVar

A_      =      TypeVar("T")






def        __UpperCAmelCase    (       UpperCAmelCase       )->       int:



   """simple docstring"""







   return (position - 1) // 2






def        __UpperCAmelCase    (       UpperCAmelCase       )->       int:



   """simple docstring"""







   return (2 * position) + 1






def        __UpperCAmelCase    (       UpperCAmelCase       )->       int:



   """simple docstring"""







   return (2 * position) + 2






class      __lowercase					(    Generic[T]    ):

      def __init__(	self				:      str   )							->		Optional[Any]:


         '''simple docstring'''

         lowercase							=		[]
         lowercase							=		{}
         lowercase							=		0

      def __len__(	self				:      Union[str, Any]   )							->		List[str]:


         '''simple docstring'''

         return self.elements

      def __repr__(	self				:      Dict   )							->		str:


         '''simple docstring'''

         return str(self.heap   )

      def        __a		(	self				:      int   )							->		Optional[Any]:


         '''simple docstring'''

         return self.elements == 0

      def        __a		(	self				:      int							,							__lowerCamelCase				:      T							,							__lowerCamelCase				:      int   )							->		Any:


         '''simple docstring'''

         self.heap.append((elem, weight)   )
         lowercase							=		self.elements
         self.elements += 1
         self._bubble_up(__lowerCamelCase   )

      def        __a		(	self				:      Union[str, Any]   )							->		int:


         '''simple docstring'''

         if self.elements > 1:
            self._swap_nodes(0							,							self.elements - 1   )
         lowercase		,lowercase							=		self.heap.pop()
         del self.position_map[elem]
         self.elements -= 1
         if self.elements > 0:
            lowercase		,lowercase							=		self.heap[0]
            self._bubble_down(__lowerCamelCase   )
         return elem

      def        __a		(	self				:      Union[str, Any]							,							__lowerCamelCase				:      T							,							__lowerCamelCase				:      int   )							->		Optional[Any]:


         '''simple docstring'''

         lowercase							=		self.position_map[elem]
         lowercase							=		(elem, weight)
         if position > 0:
            lowercase							=		get_parent_position(__lowerCamelCase   )
            lowercase		,lowercase							=		self.heap[parent_position]
            if parent_weight > weight:
               self._bubble_up(__lowerCamelCase   )
            else:
               self._bubble_down(__lowerCamelCase   )
         else:
            self._bubble_down(__lowerCamelCase   )

      def        __a		(	self				:      Optional[int]							,							__lowerCamelCase				:      T   )							->		str:


         '''simple docstring'''

         lowercase							=		self.position_map[elem]
         if curr_pos == 0:
            return None
         lowercase							=		get_parent_position(__lowerCamelCase   )
         lowercase		,lowercase							=		self.heap[curr_pos]
         lowercase		,lowercase							=		self.heap[parent_position]
         if parent_weight > weight:
            self._swap_nodes(__lowerCamelCase							,							__lowerCamelCase   )
            return self._bubble_up(__lowerCamelCase   )
         return None

      def        __a		(	self				:      int							,							__lowerCamelCase				:      T   )							->		Optional[Any]:


         '''simple docstring'''

         lowercase							=		self.position_map[elem]
         lowercase		,lowercase							=		self.heap[curr_pos]
         lowercase							=		get_child_left_position(__lowerCamelCase   )
         lowercase							=		get_child_right_position(__lowerCamelCase   )
         if child_left_position < self.elements and child_right_position < self.elements:
            lowercase		,lowercase							=		self.heap[child_left_position]
            lowercase		,lowercase							=		self.heap[child_right_position]
            if child_right_weight < child_left_weight and child_right_weight < weight:
               self._swap_nodes(__lowerCamelCase							,							__lowerCamelCase   )
               return self._bubble_down(__lowerCamelCase   )
         if child_left_position < self.elements:
            lowercase		,lowercase							=		self.heap[child_left_position]
            if child_left_weight < weight:
               self._swap_nodes(__lowerCamelCase							,							__lowerCamelCase   )
               return self._bubble_down(__lowerCamelCase   )
         else:
            return None
         if child_right_position < self.elements:
            lowercase		,lowercase							=		self.heap[child_right_position]
            if child_right_weight < weight:
               self._swap_nodes(__lowerCamelCase							,							__lowerCamelCase   )
               return self._bubble_down(__lowerCamelCase   )
         return None



      def        __a		(	self				:      List[Any]							,							__lowerCamelCase				:      int							,							__lowerCamelCase				:      int   )							->		Tuple:


         '''simple docstring'''

         lowercase							=		self.heap[nodea_pos][0]
         lowercase							=		self.heap[nodea_pos][0]
         lowercase		,lowercase							=		(
             self.heap[nodea_pos],
             self.heap[nodea_pos],
         )
         lowercase							=		nodea_pos
         lowercase							=		nodea_pos






class      __lowercase					(    Generic[T]    ):

      def __init__(	self				:      List[Any]   )							->		Union[str, Any]:


         '''simple docstring'''

         lowercase							=		{}
         lowercase							=		0

      def __repr__(	self				:      Optional[int]   )							->		Union[str, Any]:


         '''simple docstring'''

         return str(self.connections   )

      def __len__(	self				:      List[str]   )							->		Optional[Any]:


         '''simple docstring'''

         return self.nodes

      def        __a		(	self				:      Union[str, Any]							,							__lowerCamelCase				:      T   )							->		List[Any]:


         '''simple docstring'''

         if node not in self.connections:
            lowercase							=		{}
            self.nodes += 1



      def        __a		(	self				:      str							,							__lowerCamelCase				:      T							,							__lowerCamelCase				:      T							,							__lowerCamelCase				:      int   )							->		Optional[int]:


         '''simple docstring'''

         self.add_node(__lowerCamelCase   )
         self.add_node(__lowerCamelCase   )
         lowercase							=		weight
         lowercase							=		weight






def        __UpperCAmelCase    (       UpperCAmelCase,		)->       tuple[dict[T, int], dict[T, T | None]]:



   """simple docstring"""







   lowercase							=		{node: maxsize for node in graph.connections}
   lowercase							=		{node: None for node in graph.connections}

   lowercase							=		MinPriorityQueue()
   for node, weight in dist.items():
      priority_queue.push(__UpperCAmelCase,		__UpperCAmelCase       )

   if priority_queue.is_empty():
      return dist, parent

   # initialization
   lowercase							=		priority_queue.extract_min()
   lowercase							=		0
   for neighbour in graph.connections[node]:
      if dist[neighbour] > dist[node] + graph.connections[node][neighbour]:
         lowercase							=		dist[node] + graph.connections[node][neighbour]
         priority_queue.update_key(__UpperCAmelCase,		dist[neighbour]       )
         lowercase							=		node

    # running prim's algorithm
   while not priority_queue.is_empty():
      lowercase							=		priority_queue.extract_min()
      for neighbour in graph.connections[node]:
         if dist[neighbour] > dist[node] + graph.connections[node][neighbour]:
            lowercase							=		dist[node] + graph.connections[node][neighbour]
            priority_queue.update_key(__UpperCAmelCase,		dist[neighbour]       )
            lowercase							=		node
   return dist, parent






from __future__ import annotations

import math






def        __UpperCAmelCase    (       UpperCAmelCase       )->       list[int]:



			"""simple docstring"""







			if num <= 0:
						lowercase							=		f'{num}: Invalid input, please enter a positive integer.'
						raise ValueError(UpperCAmelCase       )

			lowercase							=		[True] * (num + 1)
			lowercase							=		[]
			lowercase							=		2
			lowercase							=		int(math.sqrt(UpperCAmelCase       )       )

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

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

						start += 1

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

			return prime


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





