

from __future__ import annotations

import math







def       A_				(   _UpperCAmelCase   ):

						if num <= 0:
												SCREAMING_SNAKE_CASE_:			Union[str, Any]  		=	f"{num}: Invalid input, please enter a positive integer."
												raise ValueError(_UpperCAmelCase   )

						SCREAMING_SNAKE_CASE_:			Optional[int]  		=	[True] * (num + 1)
						SCREAMING_SNAKE_CASE_:			str  		=	[]
						SCREAMING_SNAKE_CASE_:			Union[str, Any]  		=	2
						SCREAMING_SNAKE_CASE_:			int  		=	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:
																														SCREAMING_SNAKE_CASE_:			Tuple  		=	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())))








from __future__ import annotations

from collections import deque
from collections.abc import Iterator
from dataclasses import dataclass



@dataclass
class   __lowercase    :




			"""simple docstring"""







			_UpperCAmelCase       :							int
			_UpperCAmelCase       :							int







class   __lowercase    :




			"""simple docstring"""







			def __init__(			self  :					Any       ,						lowerCAmelCase__  :					int):
									SCREAMING_SNAKE_CASE_:			list[list[Edge]]  		=	[[] for _ in range(lowerCAmelCase__)]
									SCREAMING_SNAKE_CASE_:			Dict  		=	size



			def __getitem__(			self  :					Dict       ,						lowerCAmelCase__  :					int):
									return iter(self._graph[vertex])



			@property
			def 	_SCREAMING_SNAKE_CASE      (			self  :					Tuple):
									return self._size



			def 	_SCREAMING_SNAKE_CASE      (			self  :					Dict       ,						lowerCAmelCase__  :					int       ,						lowerCAmelCase__  :					int       ,						lowerCAmelCase__  :					int):
									if weight not in (0, 1):
															raise ValueError("Edge weight must be either 0 or 1.")

									if to_vertex < 0 or to_vertex >= self.size:
															raise ValueError("Vertex indexes must be in [0; size).")

									self._graph[from_vertex].append(Edge(lowerCAmelCase__       ,						lowerCAmelCase__))




			def 	_SCREAMING_SNAKE_CASE      (			self  :					List[Any]       ,						lowerCAmelCase__  :					int       ,						lowerCAmelCase__  :					int):
									SCREAMING_SNAKE_CASE_:			Optional[int]  		=	deque([start_vertex])
									SCREAMING_SNAKE_CASE_:			list[int | None]  		=	[None] * self.size
									SCREAMING_SNAKE_CASE_:			List[Any]  		=	0

									while queue:
															SCREAMING_SNAKE_CASE_:			int  		=	queue.popleft()
															SCREAMING_SNAKE_CASE_:			str  		=	distances[current_vertex]
															if current_distance is None:
																					continue

															for edge in self[current_vertex]:
																					SCREAMING_SNAKE_CASE_:			Optional[int]  		=	current_distance + edge.weight
																					SCREAMING_SNAKE_CASE_:			str  		=	distances[edge.destination_vertex]
																					if (
																					    isinstance(lowerCAmelCase__       ,						lowerCAmelCase__)
																					    and new_distance >= dest_vertex_distance
																					):
																											continue
																					SCREAMING_SNAKE_CASE_:			Any  		=	new_distance
																					if edge.weight == 0:
																											queue.appendleft(edge.destination_vertex)
																					else:
																											queue.append(edge.destination_vertex)

									if distances[finish_vertex] is None:
															raise ValueError("No path from start_vertex to finish_vertex.")

									return distances[finish_vertex]


if __name__ == "__main__":
						import doctest

						doctest.testmod()






